[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* 博客：——————————————————*/;class Solution {public:int maximumGap(vector<int> &num) {if(num.empty() || num.size() < 2){return 0;}//ifint 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];}//ifif(num[i] < Min){Min = num[i];}//if}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;}index = (num[i] – Min) / gap;bucketsMin[index] = min(bucketsMin[index], num[i]);bucketsMax[index] = max(bucketsMax[index], num[i]);}maxGap = 0;int pre = Min;for(int i = 0;i < bucketNum;++i){if(bucketsMin[i] == INT_MAX || bucketsMax[i] == INT_MIN){continue;}//ifmaxGap = max(maxGap, bucketsMin[i] – pre);pre = bucketsMax[i];}//formaxGap = 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;}

运行时间

接受失败更是一种智者的宣言和呐喊