Maximum Gap

https://leetcode.com/problems/maximum-gap/
给定一个无序int数组,求出排序后相邻两个整数最大的差值

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.

  • 解题思路
    桶排序 Bucket Sort 来做,首先找出数组的最大值和最小值,然后要确定每个桶的容量,即为 (最大值 - 最小值) / 个数 + 1,在确定桶的个数,即为 (最大值 - 最小值) / 桶的容量 + 1,然后需要在每个桶中找出局部最大值和最小值,而最大间距的两个数不会在同一个桶中,而是一个桶的最小值和另一个桶的最大值之间的间距

上代码

 public int maximumGap(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, n = nums.length, pre = 0, res = 0;
        for (int num : nums) {
            max = Integer.max(max, num);
            min = Integer.min(min, num);
        }

        //bucket的大小
        int size = (max - min) / n + 1;

        //一共有多少个bucket
        int cnt = (max - min) / size + 1;

        int[] bucketMin = new int[cnt];
        int[] bucketMax = new int[cnt];

        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        //计算每个bucket内部的最大值和最小值
        for (int num : nums) {
            int idx = (num - min) / size;
            bucketMin[idx] = Math.min(bucketMin[idx], num);
            bucketMax[idx] = Math.max(bucketMax[idx], num);
        }

        for (int i = 1; i < cnt; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE || bucketMax[i] == Integer.MIN_VALUE){
                continue;
            }

            res = Math.max(res,bucketMin[i] - bucketMax[pre]);
            pre = i;
        }

        return res;
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。