164. Maximum Gap

EddieChan 发布于2019-08-14 14:09 / 2999人阅读

摘要：这个的长度是最小可能的最大差值。注意考虑和两个边界值也要加进去。

题目：
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;
    }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64837.html

leetcode164. Maximum Gap

摘要：这里最小的意思并不是说任意两个数之间的最小间隔，而是指这一组数字的最大间隔必然不小于这个最小间隔。而每个桶内的数字间隔必然不会超过最小间隔。题目要求 Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve...

张利勇 2019-08-15 14:18 评论0 收藏0
深入理解 CSS：字体度量、line-height 和 vertical-align

摘要：接下来说句听起来很奇怪的话一个内联元素有两个高度高度和实际区域高度是我自己发明的单词，它表示对人类有效的高度，你在其他地方是看不到这个单词的。你没看错，是计算的一些细节对于内联元素，和会增大区域，但是不会增大不是的高度。本文为饥人谷讲师方方原创文章，首发于前端学习指南。这是一篇译文，对 inline 和 inline-block 的元素剖析非常给力。原文：Deep dive C...

Dean 2019-08-29 14:04 评论0 收藏0
MongoDB （五）高级_索引

摘要：插入两条数据建立全文索引需要注意的是这里使用关键词来代表全文索引，我们在这里就不建立数据模型了。全文索引查找表示要在全文索引中查东西。全文索引在工作还是经常使用的，比如博客文章的搜索，长文件的关键词搜索，这些都需要使用全文索引来进行。索引在认识索引的之前我们先建立一张表，并往其中插入200万条数据。 // test.js //生成随机数 function GetRandomNum(...

focusj 2019-06-26 17:38 评论0 收藏0
2018年全球云市场达到2500亿美元：增长放缓自然，但繁荣“将继续”。

摘要：全球云市场在年达到亿美元增长放缓是自然的，但随着新年的到来，繁荣将继续推特，这标志着评估行业格局的最佳时机。根据的最新报告，年全球云市场达到亿美元亿美元，年增长率为。此外，超尺度资本支出超过亿美元，比年前三季度增长了。全球云市场在2018年达到2500亿美元：增长放缓是自然的，但随着新年的到来，繁荣将继续推特，这标志着评估行业格局的最佳时机。根据Synergy Research的最新报告，2...

jas0n 2019-03-21 15:45 评论0 收藏0