164. Maximum Gap

1.問題

• 給予一個array, 找出兩兩間最大的差值

2.想法

• 練習bucket sort:

  • 先計算list的數值分布區間

  • bucket區間是(max - min) / (num - 1), 也是預設的答案

  • 分組:

    • 用map作為有序容器來存放區間最大值, 區間最小值

3.程式碼

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size = nums.size();
        if (size < 2) 
        {
            return 0;
        }
        
        int maxNum = nums[0];
        int minNum = nums[0];
        for(int i = 0; i < size; i++)
        {
            if (nums[i] < minNum)
            {
                minNum = nums[i];
            }
            if (nums[i] > maxNum)
            {
                maxNum = nums[i];
            }
        }
        
        //Bucket size
        int bucketSize = (maxNum - minNum)/(size - 1);
        //Default answer is bucket size
        int ans = bucketSize;
        //bucketSize + 1, if the members are the same
        if (bucketSize == 0)
        {
            bucketSize++;
        }
        
        //Grouping
        map<int, int> bucketLargest;
        map<int, int> bucketSmallest;
        for(int i = 0; i < size; i++)
        {
            int bucketIndex = nums[i] / bucketSize;
            if (bucketLargest.find(bucketIndex) != bucketLargest.end())
            {
                if (nums[i] > bucketLargest[bucketIndex])
                {
                    bucketLargest[bucketIndex] = nums[i];   
                }
            }
            else
            {
                bucketLargest[bucketIndex] = nums[i];
            }
            
            if (bucketSmallest.find(bucketIndex) != bucketSmallest.end())
            {
                if (nums[i] < bucketSmallest[bucketIndex])
                {
                    bucketSmallest[bucketIndex] = nums[i];   
                }
            }
            else 
            {
                bucketSmallest[bucketIndex] = nums[i];
            }
        }
        
        int start = minNum / bucketSize;
        int lastLargest = bucketLargest[start];
        for (int i = start + 1; i <= maxNum / bucketSize; i++)
        {
            if (bucketSmallest.find(i) != bucketSmallest.end())
            {
                ans = max(ans, bucketSmallest[i] - lastLargest);
                lastLargest = bucketLargest[i];
            }
        }
        return ans;
    }
};

4.Performance