leetcode164. Maximum Gap

张利勇发布于2019-08-15 14:18 / 2748人阅读

摘要：这里最小的意思并不是说任意两个数之间的最小间隔，而是指这一组数字的最大间隔必然不小于这个最小间隔。而每个桶内的数字间隔必然不会超过最小间隔。

题目要求

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.

一个乱序的数组，找到其有序排列后相邻两个数之间最大的间隔。试着用线性时间和空间复杂度来解决这个问题。

思路和代码

这里并不需要完全的进行排序。我们只需要找到合适的区间划分，并将各个数字丢到其所属的区间中。之后，我们只需要比较前一个区间的最大值和后一个区间的最小值之间的差距即可以获得该数组最大的间隔。

这里选择区间划分的方式是找到这一组数字的“最小”间隔。这里最小的意思并不是说任意两个数之间的最小间隔，而是指这一组数字的最大间隔必然不小于这个最小间隔。
我们可以知道，假设有n个数字，那么这n个数字的最小间隔为Math.ceil((double)(max-min) / (count-1))，即将最大值和最小值的差距按照数组大小等分。

可以将其想象为爬楼梯，我们从最小的数字试图爬到最大的数字，一共有n-1级台阶，而且每个台阶的高度为整数。那么一旦有一级台阶比最小间隔矮，就必然有一级比最小间隔高，从而才能爬到最大的数字。

因此，我们现在相当于分出了n个桶，每个数字必然落入这n个桶中的一个。而每个桶内的数字间隔必然不会超过最小间隔。所以正如上文所说，比较相邻两个桶的边界就可以了。

    public int maximumGap(int[] nums) {
        int count = nums.length;
        if(count < 2) return 0;
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int num : nums){
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        
        int minGap = (int)Math.ceil((max - min) * 1.0 / (count - 1));
        if(minGap==0) return minGap;
        int[] minBucket = new int[count];
        int[] maxBucket = new int[count];
        for(int i = 0 ; i maxBucket[i]) continue;
            maxGap = Math.max(minBucket[i] - prev, maxGap);
            prev = maxBucket[i];
        }
        
        return maxGap;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Maximum Gap Leetcod LeetCode

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

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

164. Maximum Gap

摘要：这个的长度是最小可能的最大差值。注意考虑和两个边界值也要加进去。题目：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...

EddieChan 2019-08-14 14:09 评论0 收藏0
Leetcode PHP题解--D47 868. Binary Gap

摘要：题目链接题目分析给定一个数字，计算其二进制表示中，出现的两个最大距离。因为只有一个是没办法比较距离的。当出现时，判断当前距离是否大于记录的最大值。最后判断当只有一个时，直接返回。否则返回所记录的最大距离。 D47 868. Binary Gap 题目链接 868. Binary Gap 题目分析给定一个数字，计算其二进制表示中，出现的两个1最大距离。思路当然是先转换成二进制了。再...

Flink_China 2019-07-01 12:44 评论0 收藏0
[LeetCode] Third Maximum Number

Problem Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example Example 1: Inp...

red_bricks 2019-08-19 10:58 评论0 收藏0
[LeetCode] Maximum Binary Tree

Problem Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array.The left subtree is the maximum tree construc...

xiaoqibTn 2019-08-15 15:59 评论0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉树最大深度

LeetCode 104 Maximum Depth of Binary Tree难度：Easy 题目描述：找到一颗二叉树的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...

PiscesYE 2019-08-16 13:28 评论0 收藏0