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

╰+哭是因爲堅強的太久メ 2022-06-08 07:25 121阅读 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.

这道题就是在一个无序的数组中寻找最大的相邻元素的Gap，最直接的方法就是先排序。然后遍历即可。

但是这不是本体的要求，我想了很久没想出来，看了网上的答案，才明白这道题考查的是桶排序，根据数组的最大值最小值的落差以及元素的数量，分配一定数量的桶，然后比较相邻桶的最小值和最大值（上一个桶的最大值和下一个桶的最小值一定是相邻的）就可以得出最大的相邻元素的Gap。

注意这道题是桶排序的一个很好的示范，很值得学习。

代码如下：

import java.util.Arrays;
    
    
    /*
     * http://blog.csdn.net/tofu_jelly/article/details/43339305
     * 
     * 借鉴桶排序
     * 
     * */
    public class Solution 
    {
        public int maximumGap(int[] nums) 
        {
            if(nums==null || nums.length<=1)
                return 0;
    
            int maxNum=Integer.MIN_VALUE,minNum=Integer.MAX_VALUE;
            for(int i=0;i<nums.length;i++)
            {
                maxNum=Math.max(maxNum, nums[i]);
                minNum=Math.min(minNum, nums[i]);
            }
            if(nums.length==2)
                return maxNum-minNum;
    
            //元素之间的最大间隔，注意向上取整
            int averageGap = (int)Math.ceil((double)(maxNum-minNum)/(nums.length-1));
    
            //这个是处理元素都相等的情况
            if(averageGap==0)
                return 0;
    
            int numOfBuckets = (maxNum-minNum)/averageGap +1;
            int []minBuck=new int[numOfBuckets];
            Arrays.fill(minBuck, Integer.MAX_VALUE);
            int []maxBuck=new int[numOfBuckets];
            Arrays.fill(maxBuck, Integer.MIN_VALUE);
    
            //minBuck和maxBuch放的是对应的最大值和最小值
            for(int i=0;i<nums.length;i++)
            {
                int index=(nums[i]-minNum) / averageGap;
                minBuck[index] = Math.min(minBuck[index], nums[i]);
                maxBuck[index] = Math.max(maxBuck[index], nums[i]);
            }
    
            int maxGap = Integer.MIN_VALUE;
            //上一个桶的最大值和下一个桶的最小值肯定是相邻的，所以才可能存在最大的gap
            int pre=maxBuck[0];
            for(int i=0;i<numOfBuckets;i++)
            {
                //桶为空的情况
                if(minBuck[i]==Integer.MAX_VALUE && maxBuck[i]==Integer.MIN_VALUE)
                    continue;
                else
                {
                    maxGap=Math.max(maxGap,minBuck[i]-pre);
                    pre=maxBuck[i];
                }   
            }
            return maxGap;
        }
    
        /*
         * 使用排序做的答案
         * */
        public int maximumGapUseSort(int[] nums) 
        {
            if(nums==null || nums.length<=1)
                return 0;
    
            Arrays.sort(nums);
            int maxGap=0;
    
            for(int i=1;i<nums.length;i++)
                maxGap=Math.max(nums[i]-nums[i-1], maxGap);
    
            return maxGap;
        }
    }

下面是C++的做法，这道题是桶排序的一个很好的应用

代码如下：

#include <iostream>
    #include <algorithm>
    #include <climits>
    #include <vector>
    
    using namespace std;
    
    
    //  164. Maximum Gap
    class Solution 
    {
    public:
        int maximumGap(vector<int>& nums)
        {
            if (nums.size() <= 1)
                return 0;
    
            int minNum = nums[0], maxNum = nums[0];
            for (int a : nums)
            {
                minNum = min(minNum, a);
                maxNum = max(maxNum, a);
            }
            if (nums.size() == 2)
                return maxNum - minNum;
    
            int averageGap = (int)ceil((double)(maxNum - minNum)/(nums.size()-1));
            if (averageGap == 0)
                return 0;
    
            int numBucks = (maxNum - minNum) / averageGap + 1;
            vector<int> minBuck(numBucks, numeric_limits<int>::max());
            vector<int> maxBuck(numBucks, numeric_limits<int>::min());
            for (int a : nums)
            {
                int index = (a - minNum) / averageGap;
                minBuck[index] = min(minBuck[index], a);
                maxBuck[index] = max(maxBuck[index], a);
            }
    
            int maxGap = numeric_limits<int>::min();
            int pre = maxBuck[0];
            for (int i = 0; i < numBucks; i++)
            {
                if (minBuck[i] == numeric_limits<int>::max()
                    && maxBuck[i] == numeric_limits<int>::min())
                    continue;
                else
                {
                    maxGap = max(maxGap,minBuck[i] - pre);
                    pre = maxBuck[i];
                }
            }
            return maxGap;
        }
    };