HelloKenLee

Leetcode 624. Maximum Distance in Arrays 解题报告

Posted on By KenLee

题目信息

题目: 624. Maximum Distance in Arrays
难度: Easy
正确率: 29.8%
问题描述:
Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference a-b . Your task is to find the maximum distance.

Example 1:

Input: 
[[1,2,3],
 [4,5],
 [1,2,3]]
Output: 4

**Explanation: ** One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

  1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
  2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
  3. The integers in the m arrays will be in the range of [-10000, 10000].

问题分析

  该问题的意思是,给出个升序的数组,要你找出不同数组之间差距最大的两个数,返回其差距。注意一定要是不同数组,同一数组不算,差距的计算方式为两个数的差的绝对值。

  数组中的数的范围为[-10000,1000],数组中元素的个数为[2,10000]

解题思路

  (没想到我堕落到写easy题的题解了啊…更没想到我easy题还WA了两次TLE了一次啊!!!)

  (其实是因为考试复习想找到水题刷了,没想到这道题还挺有意思的。)

  一开始看到以为是求解最小差距,感觉要以每个数为单位处理。后来才发现要求最大差距,仔细的思考了一下,因为数组内部是升序,因此我们可以把每一个数组想象成数轴上的一个闭区间:数组间的最大差距只可能发生在数组的首尾元素上,因为差距最大的两个数肯定会是某一个数组的头和某一个数组的尾。因此一开始我就把每一个数组的头,尾和其他数组的头尾比较,记录最大的差距。结果这种方法是TLE的,因为每一个数组的头尾都需要和其他数组的头尾比较,所以会有$O(M^2)$的复杂度。

  一个改进的方法是把所有数组的头尾都放到一个数组里面,然后sort()一次,取出头尾两个数相减就是最大差距了。这种方法比较tricky的地方就是需要判断最大差距的头尾两个数是否属于同一个数组。我是采用一个哈希表来判断, hash<key = front, value = back>记录某个数字作为第一个元素对应的最大的最后一个元素是多少。 之后在根据是否同一个数组的信息来判定是否取排序后的数组的哪两个数来求差距。这种方法能过,时间复杂度为$O(MlogM)$

  后来想到更好的方法,不需要排序,我们只需要在遍历数组们的头尾的过程中记录4个数:最小的数,第二小的数,最大的数,第二大的数。 同时记录哈希表。 这样后面采取类似的方法处理。时间复杂度为$O(M)$。

结果分析

  • 时间复杂度: $ O(M) $ 假设M表示数组的个数。
  • 空间复杂度: $ O(M) $ 哈希表大小+常数空间。
  • 通过时间: 25 ms
  • 击败: ??(直至提交时还没有足够数据统计)

源代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        vector<int> distArray;
        unordered_map<int, int> sameArray;
        for(auto array:arrays) {
            distArray.push_back(array.front());
            distArray.push_back(array.back());
            auto it = sameArray.find(array.front());
            if(it != sameArray.end()){
                // 哈希表有这一项, 存距离大的
                it->second = max(it->second, array.back());
            } else {
                // 没有这一项, 新建这一项
                sameArray.insert(make_pair(array.front(), array.back()));
            }
        }
        sort(distArray.begin(), distArray.end());
        int maxDist = distArray.back() - distArray.front();
        if(sameArray[distArray.front()] == distArray.back()){
            // 如果最大距离是同一个数组
            maxDist = max(distArray.back() - distArray[1], distArray[distArray.size() - 2] - distArray.front());
        }
        return maxDist;
    }
};