[LeetCode] Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

• 解题思路1
  先排序后比较相邻元素插值。
• 实现代码1

/*****************************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/7 12:19
    *  @Status   : Accepted
    *  @Runtime  : 28 ms
*****************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2)
        {
            return 0;
        }
        sort(num.begin(),num.end());
        int max = 0;
        int n;
        for (int i = 1; i < num.size(); i++)
        {
            n = num[i] - num[i - 1];
            max = max > n ? max : n;
        }
        return max;
    }
};

• 解题思路2
  • 假设有取值范围为A到B的N个元素，则他们的最大gap不会小于celling[(B - A) / (N - 1)]。
  • 让桶的长度len = celling[(B - A) / (N - 1)]，则我们最多会有num = (B - A) / len + 1个桶。
  • 对于数组中的任意元素K，我们可以通过计算toc = (K - A) / len轻松的找到它属于哪一个桶，然后我们维护每个桶中的最大值和最小值。
  • 由于同一个桶中元素的最大差值是len - 1，所有最后的答案不会是来自同一个桶中的两个元素。
  • 对于每一个非空的桶p，找到下一个非空的桶q，然后q.min - p.max就是该问题的潜在的最大值。返回这些值的最大值。
• 实现代码2

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/9 19:31
    *  @Status   : Accepted
    *  @Runtime  : 13 ms
******************************************************************/
class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2)
        {
            return 0;
        }
        int maxNum = *max_element(num.begin(), num.end());
        int minNum = *min_element(num.begin(), num.end());
        int gap = ceil((double)(maxNum - minNum) / (num.size() - 1));
        int bucketCount = (maxNum - minNum) / gap + 1;
        vector<int> bucketMax(bucketCount, INT_MIN);
        vector<int> bucketMin(bucketCount, INT_MAX);

        int bucketIndex;
        //put into buckets
        for (int i = 0; i < num.size(); i++)
        {
            if (num[i] != maxNum && num[i] != minNum)
            {
                bucketIndex = (num[i] - minNum) / gap;
                bucketMax[bucketIndex] = max(num[i], bucketMax[bucketIndex]);
                bucketMin[bucketIndex] = min(num[i], bucketMin[bucketIndex]);
            }
        }

        int previous = minNum;
        int maxGap = INT_MIN;
        for (int j = 0; j < bucketCount; j++)
        {
            if (bucketMax[j] == INT_MIN && bucketMin[j] == INT_MAX)
            {
                continue;  //empty bucket
            }
            maxGap = max(maxGap, bucketMin[j] - previous);
            previous = bucketMax[j];
        }
        maxGap = max(maxGap, maxNum - previous);

        return maxGap;
    }
};

将上述代码注释掉一部分代码，依然是可行的。个人认为这样可以减少一部分判断过程。

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/9 19:31
    *  @Status   : Accepted
    *  @Runtime  : 14 ms
******************************************************************/
class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2)
        {
            return 0;
        }
        int maxNum = *max_element(num.begin(), num.end());
        int minNum = *min_element(num.begin(), num.end());
        int gap = ceil((double)(maxNum - minNum) / (num.size() - 1));
        int bucketCount = (maxNum - minNum) / gap + 1;
        vector<int> bucketMax(bucketCount, INT_MIN);
        vector<int> bucketMin(bucketCount, INT_MAX);

        int bucketIndex;
        for (int i = 0; i < num.size(); i++)
        {
            /*if (num[i] != maxNum && num[i] != minNum)
            {*/
                bucketIndex = (num[i] - minNum) / gap;
                bucketMax[bucketIndex] = max(num[i], bucketMax[bucketIndex]);
                bucketMin[bucketIndex] = min(num[i], bucketMin[bucketIndex]);
            /*}*/
        }

        int previous = minNum;
        int maxGap = INT_MIN;
        for (int j = 0; j < bucketCount; j++)
        {
            if (bucketMax[j] == INT_MIN && bucketMin[j] == INT_MAX)
            {
                continue;  //empty bucket
            }
            maxGap = max(maxGap, bucketMin[j] - previous);
            previous = bucketMax[j];
        }
        /*maxGap = max(maxGap, maxNum - previous);*/

        return maxGap;
    }
};