maximum gap java_164. Maximum Gap

àì夳堔傛蜴生んèń 2022-11-08 11:24 146阅读 0赞

题目：

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.

解答：

这题挺难理解的，但是可以举例，比如说现在有1, 3, 5, 9。那么我们可以把它分成3个bucket来装，min表示在这个bucket范围中，存在的最小数和最大数。这个bucket的长度是最小可能的最大差值。(如果哪个差值比这个还小，那么为了填补这个小差值，就必然存在另一个差值比它大，那么这个数组的最大差值就比当前bucket大。所以均分下来的bucket是最小可能的最大差值)

b0: (1, 3) min = Integer.max, max = Integer.min

b1: (4, 6) min = Integer.max, max = Integer.min

b2: (7, 9) min = Integer.max, max = Integer.min

然后我们来看这个数组里的数在哪个bucket里，用(nums(i) - min) / gap来得到，

第一个数1在b0中，所以我们更新:

b0: (1, 3) min = 1, max = 1;

第二个数3在b0中，所以我们更新：

b0: (1, 3) min = 1, max = 3;

第三个数5在b1中，所以我们更新：

b1: (4, 6) min = 5, max = 5;

.

.

依次这样下去。

因为每个bucket中的最大值－最小值就是我们最小的gap, 所以我们不用计算相邻的两个数，我们只要比较后一个bucket中的最小值和前一个bucket中的最大值相差多少，取最大相差的值就是最终的结果。注意考虑min和max两个边界值也要加进去。

public int maximumGap(int\[\] nums) \{

if (nums == null || nums.length < 2) return 0;

int len = nums.length;

int max = nums\[0\], min = nums\[0\];

for (int i = 0; i < nums.length; i++) \{

max = Math.max(max, nums\[i\]);

min = Math.min(min, nums\[i\]);

\}

//Math.ceil与最小的比这个数大的蒸熟，使bucket可以包含所有数

int gap = (int)Math.ceil((double)(max - min) / (len - 1));

int\[\] BucketsMIN = new int\[len - 1\];

int\[\] BucketsMAX = new int\[len - 1\];

Arrays.fill(BucketsMIN, Integer.MAX\_VALUE);

Arrays.fill(BucketsMAX, Integer.MIN\_VALUE);

for (int num : nums) \{

//不考虑边界，所以把边界的min和max都拿出来，单独再考虑

if (num == min || num == max) continue;

int bucket = (num - min) / gap;

BucketsMIN\[bucket\] = Math.min(BucketsMIN\[bucket\], num);

BucketsMAX\[bucket\] = Math.max(BucketsMAX\[bucket\], num);

\}

int result = 0;

int previous = min;

for (int i = 0; i < len - 1; i++) \{

if (BucketsMIN\[i\] == Integer.MAX\_VALUE && BucketsMAX\[i\] == Integer.MIN\_VALUE) \{

continue;

\}

result = Math.max(result, BucketsMIN\[i\] - previous);

previous = BucketsMAX\[i\];

\}

result = Math.max(result, max - previous);

return result;

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关间隙锁(Gap Lock)

一.什么是[间隙锁][Link 1]？间隙锁（[Gap][] Lock）：当我们用范围条件而不是相等条件索引数据，并请求共享或排他锁时，InnoDB会给符合条件的已有数

心已赠人/ 2024年03月24日 18:18/ 0 赞/ 70 阅读

相关 maximum gap java_164. Maximum Gap

题目： Given an unsorted array, find the maximum difference between the successive element

àì夳堔傛蜴生んèń/ 2022年11月08日 11:24/ 0 赞/ 147 阅读

相关 leetcode 164. Maximum Gap | 164. 最大间距（桶排序）

题目 [https://leetcode.com/problems/maximum-gap/][https_leetcode.com_problems_maximum-g

港控/mmm°/ 2022年09月11日 01:14/ 0 赞/ 60 阅读

相关 Maximum Gap（C++最大间距）

（1）排序 class Solution { public: int maximumGap(vector<int>& nums) {

小咪咪/ 2022年08月29日 13:51/ 0 赞/ 178 阅读

相关 Maximum Gap --LeetCode

Given an unsorted array, find the maximum difference between the successive elements in

素颜马尾好姑娘i/ 2022年08月07日 12:58/ 0 赞/ 151 阅读

相关 leetcode Maximum Gap

题目 Given an unsorted array, find the maximum difference between the successive elemen

曾经终败给现在/ 2022年08月05日 01:24/ 0 赞/ 163 阅读

相关 LeetCode164—Maximum Gap

原题 [原题链接][Link 1] > Given an unsorted array, find the maximum difference between the

ゝ一世哀愁。/ 2022年07月13日 22:38/ 0 赞/ 58 阅读

相关 leetcode 164. Maximum Gap 相邻元素的最大间隔 + 一个很好的桶排序示范

Given an unsorted array, find the maximum difference between the successive elements in

╰+哭是因爲堅強的太久メ/ 2022年06月08日 07:25/ 0 赞/ 164 阅读

相关 LeetCode 164.Maximum Gap (最大间距)

题目描述：给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。示例 1: 输入: [3,6,9,1]

淩亂°似流年/ 2022年05月10日 14:50/ 0 赞/ 155 阅读

相关 [Leetcode] Maximum Gap

Maximum Gap Given an unsorted array, find the maximum difference between the successive

布满荆棘的人生/ 2021年12月03日 07:11/ 0 赞/ 163 阅读