double check 400. Maximum Gap

class Solution { public:

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

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.

Have you met this question in a real interview?  

Example

Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

/** * @param nums: an array of integers * @return: the maximun difference */ int maximumGap(vector<int> &nums) { // write your code here // O(n) bucket sort // 思想就是分组，然后不是各元素比较，二是组比较 // 1，找到最大值，最小值 // 2, 所要找的GAP >= (max - min) / size + 1，即平均的GAP。如果每个bucket的容量
是这个平均GAP，所要的bucket个数是 (max - min) / 平均GAP。
// 3, 遍历数组，判断每个元素属于哪个bucket。每个bucket中只需要存属于该bucket的最大和最小值。 //4, potential的最大GAP是相邻两个bucket的最小和最大值之差。 int res = 0; int sizeN = nums.size(); if(sizeN < 2){ return 0; } int minVal = INT_MAX; int maxVal = INT_MIN; for(int i = 0; i < sizeN; i++){ minVal = min(minVal, nums[i]); maxVal = max(maxVal, nums[i]); } int averGap = (maxVal - minVal) / sizeN + 1; vector<vector<int>> bucket((maxVal - minVal) / averGap + 1); for(int i = 0; i < sizeN; i++){ int bucketId = (nums[i] - minVal) / averGap; if(bucket[bucketId].empty()){ bucket[bucketId].reserve(2); bucket[bucketId].push_back(nums[i]); bucket[bucketId].push_back(nums[i]); } else{ bucket[bucketId][0] = min(bucket[bucketId][0], nums[i]); bucket[bucketId][1] = max(bucket[bucketId][1], nums[i]); } } int pre = 0; // the first bucket must have the elements for(int i = 1; i < bucket.size(); i++){ if(!bucket[i].empty()){ res = max(res, bucket[i][0] - bucket[pre][1]); pre = i; } } return res; } };