重庆网站设计开发培训,软文代写多少钱一篇,关于网站的建设,网站搜索排名高怎么做文章目录1. 题目2. 解题2.1 暴力超时2.2 优化1. 题目
给定 m 个数组#xff0c;每个数组都已经按照升序排好序了。 现在你需要从两个不同的数组中选择两个整数#xff08;每个数组选一个#xff09;并且计算它们的距离。 两个整数 a 和 b 之间的距离定义为它们差的绝对值 |…
文章目录1. 题目2. 解题2.1 暴力超时2.2 优化1. 题目
给定 m 个数组每个数组都已经按照升序排好序了。 现在你需要从两个不同的数组中选择两个整数每个数组选一个并且计算它们的距离。 两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
示例 1
输入
[[1,2,3],[4,5],[1,2,3]]
输出 4
解释
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1
同时从第二个数组中选择 5 。注意
每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。
所有 m 个数组中的数字总数目在范围 [2, 10000] 内。
m 个数组中所有整数的范围在 [-10000, 10000] 内。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-distance-in-arrays 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 暴力超时
120 / 124 个通过测试用例
class Solution {
public:int maxDistance(vectorvectorint arrays) {int i, j, maxdis 0, n arrays.size();for(i 0; i n; i){for(j i1; j n; j){maxdis max(maxdis, abs(arrays[i].front()-arrays[j].back()));maxdis max(maxdis, abs(arrays[j].front()-arrays[i].back()));}}return maxdis;}
};2.2 优化
判断过了的数组可以进行合并只有合并以后的 最大的值最小的值 起作用
class Solution {
public:int maxDistance(vectorvectorint arrays) {int i, j, maxdis 0, n arrays.size();int MAX arrays[0].back(), MIN arrays[0].front();for(i 1; i n; i){maxdis max(maxdis, abs(arrays[i].front()-MAX));maxdis max(maxdis, abs(arrays[i].back()-MIN));MIN min(MIN, arrays[i].front());MAX max(MAX, arrays[i].back());}return maxdis;}
};56 ms 16.5 MB 长按或扫码关注我的公众号一起加油、一起学习进步
