LeetCode-164. Maximum Gap

LeetCode-164. Maximum Gap

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.

Example 1:

Input: [3,6,9,1]Output: 3Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]Output: 0Explanation: The array contains less than 2 elements, therefore return 0.

题解：

最初没想到桶排序算法，只能Onlogn完成，看了讨论区，学习了桶排序，很高效的排序算法，但是对于海量数据并不适用，空间复杂度太高。

桶排序算法：​​Solution {public: int bucketSort(vector& nums, int n) { int maxi = nums[0], mini = nums[0]; for (int i = 1; i < n; i++) { maxi = max(maxi, nums[i]); mini = min(mini, nums[i]); } int gap = max((maxi - mini)/(n - 1), 1); int m = (maxi - mini) / gap + 1; vector bucketMax(m, INT_MIN); vector bucketMin(m, INT_MAX); for (int i = 0; i < n; i++) { int k = (nums[i] - mini) / gap; if (nums[i] < bucketMin[k]) { bucketMin[k] = nums[i]; } if (nums[i] > bucketMax[k]) { bucketMax[k] = nums[i]; } } gap = bucketMax[0] - bucketMin[0]; int i = 0; while (i < m) { int j = i + 1; while (j < m && bucketMax[j] == INT_MIN && bucketMin[j] == INT_MAX) { j++; } if (j == m) { break; } gap = max(gap, bucketMin[j] - bucketMax[i]); i = j; } return gap; } int maximumGap(vector& nums) { int n = nums.size(); if (n < 2) { return 0; } return bucketSort(nums, n); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。