AM 400. Maximum Gap
Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @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的最小和最大值之差。 // maxGap一定是大于或等于avg的,所以maxGap不会出现在bucket里面,二是两个bucket之间。 const int size = nums.size(); if (size < 2 ){ return 0 ; } int minVal = INT_MAX; int maxVal = INT_MIN; for ( auto i : nums){ minVal = min(minVal, i); maxVal = max(maxVal, i); ...