[LeetCode]164.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.

思路

利用桶排序思想：
假设有N个元素数组array,最大值为Max,最小值为Min。
那么最大差值不会大于ceiling[(Maz - Min) / (N - 1)]。

令bucket（桶）的大小len = ceiling[(Maz - Min) / (N - 1)]，则最多会有(Max - Min) / len + 1个桶
对于数组中的任意整数K，很容易通过算式index = (K - Min) / len找出其桶的位置，然后维护每一个桶的最大值和最小值。

由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。
对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

代码

/*------------------------------------------------
*   日期：2015-03-23
*   作者：SJF0115
*   题目: 164.Maximum Gap
*   来源：https://leetcode.com/problems/maximum-gap/
*   结果：AC
*   来源：LeetCode
*   博客：
------------------------------------------------------*/
#include <iostream>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;

class Solution {
public:
    int maximumGap(vector<int> &num) {
        if(num.empty() || num.size() < 2){
            return 0;
        }//if
        int size = num.size();
        // 统计最大值和最小值
        int Min = num[0];
        int Max = num[0];
        for(int i = 1;i < size;++i){
            if(num[i] > Max){
                Max = num[i];
            }//if
            if(num[i] < Min){
                Min = num[i];
            }//if
        }//for
        // 最大差值
        int gap = (int)ceil((double)(Max - Min)/(size - 1));
        // 桶个数
        int bucketNum = (int)ceil((double)(Max - Min)/gap);
        // 每个桶都维护一个最大值和最小值
        vector<int> bucketsMin(bucketNum, INT_MAX);
        vector<int> bucketsMax(bucketNum, INT_MIN);
        for(int i = 0; i < size;++i){
            if(num[i] == Max || num[i] == Min){
                continue;
            }//if
            // 位于哪个桶
            int index = (num[i] - Min) / gap;
            bucketsMin[index] = min(bucketsMin[index], num[i]);
            bucketsMax[index] = max(bucketsMax[index], num[i]);
        }//for
        // 计算最大差值
        int maxGap = 0;
        int pre = Min;
        for(int i = 0;i < bucketNum;++i){
            if(bucketsMin[i] == INT_MAX || bucketsMax[i] == INT_MIN){
                continue;
            }//if
            maxGap = max(maxGap, bucketsMin[i] - pre);
            pre = bucketsMax[i];
        }//for
        maxGap = max(maxGap,Max - pre);
        return maxGap;
    }
};

int main() {
    Solution solution;
    vector<int> vec = {4,2,1,9,5,11};
    cout<<solution.maximumGap(vec)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>