c/c++语言开发共享C++实现LeetCode(164.求最大间距)

[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: 3
explanation: 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: 0
explanation: the array contains less than 2 elements, therefore return 0.

note:

• you may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
• try to solve it in linear time/space.

遇到这类问题肯定先想到的是要给数组排序，但是题目要求是要线性的时间和空间，那么只能用桶排序或者基排序。这里用桶排序 bucket sort 来做，首先找出数组的最大值和最小值，然后要确定每个桶的容量，即为 (最大值 – 最小值) / 个数 + 1，在确定桶的个数，即为 (最大值 – 最小值) / 桶的容量 + 1，然后需要在每个桶中找出局部最大值和最小值，而最大间距的两个数不会在同一个桶中，而是一个桶的最小值和另一个桶的最大值之间的间距，这是因为所有的数字要尽量平均分配到每个桶中，而不是都拥挤在一个桶中，这样保证了最大值和最小值一定不会在同一个桶中，具体的证明博主也不会，只是觉得这样想挺有道理的，各位看官大神们若知道如何证明请务必留言告诉博主啊，参见代码如下：

  class solution {  public:      int maximumgap(vector<int>& nums) {          if (nums.size() <= 1) return 0;          int mx = int_min, mn = int_max, n = nums.size(), pre = 0, res = 0;          for (int num : nums) {              mx = max(mx, num);              mn = min(mn, num);          }          int size = (mx - mn) / n + 1, cnt = (mx - mn) / size + 1;          vector<int> bucket_min(cnt, int_max), bucket_max(cnt, int_min);          for (int num : nums) {              int idx = (num - mn) / size;              bucket_min[idx] = min(bucket_min[idx], num);              bucket_max[idx] = max(bucket_max[idx], num);          }          for (int i = 1; i < cnt; ++i) {              if (bucket_min[i] == int_max || bucket_max[i] == int_min) continue;              res = max(res, bucket_min[i] - bucket_max[pre]);              pre = i;          }          return res;      }  };

github 同步地址：

参考资料：

到此这篇关于c++实现leetcode(164.求最大间距)的文章就介绍到这了,更多相关c++实现求最大间距内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！

需要了解更多c/c++开发分享C++实现LeetCode(164.求最大间距)，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!