leetcode164. Maximum Gap

張利勇發(fā)布于2019-08-15 14:18 / 2820人閱讀

摘要：這里最小的意思并不是說任意兩個(gè)數(shù)之間的最小間隔，而是指這一組數(shù)字的最大間隔必然不小于這個(gè)最小間隔。而每個(gè)桶內(nèi)的數(shù)字間隔必然不會(huì)超過最小間隔。

題目要求

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.

一個(gè)亂序的數(shù)組，找到其有序排列后相鄰兩個(gè)數(shù)之間最大的間隔。試著用線性時(shí)間和空間復(fù)雜度來解決這個(gè)問題。

思路和代碼

這里并不需要完全的進(jìn)行排序。我們只需要找到合適的區(qū)間劃分，并將各個(gè)數(shù)字丟到其所屬的區(qū)間中。之后，我們只需要比較前一個(gè)區(qū)間的最大值和后一個(gè)區(qū)間的最小值之間的差距即可以獲得該數(shù)組最大的間隔。

這里選擇區(qū)間劃分的方式是找到這一組數(shù)字的“最小”間隔。這里最小的意思并不是說任意兩個(gè)數(shù)之間的最小間隔，而是指這一組數(shù)字的最大間隔必然不小于這個(gè)最小間隔。
我們可以知道，假設(shè)有n個(gè)數(shù)字，那么這n個(gè)數(shù)字的最小間隔為Math.ceil((double)(max-min) / (count-1))，即將最大值和最小值的差距按照數(shù)組大小等分。

可以將其想象為爬樓梯，我們從最小的數(shù)字試圖爬到最大的數(shù)字，一共有n-1級(jí)臺(tái)階，而且每個(gè)臺(tái)階的高度為整數(shù)。那么一旦有一級(jí)臺(tái)階比最小間隔矮，就必然有一級(jí)比最小間隔高，從而才能爬到最大的數(shù)字。

因此，我們現(xiàn)在相當(dāng)于分出了n個(gè)桶，每個(gè)數(shù)字必然落入這n個(gè)桶中的一個(gè)。而每個(gè)桶內(nèi)的數(shù)字間隔必然不會(huì)超過最小間隔。所以正如上文所說，比較相鄰兩個(gè)桶的邊界就可以了。

    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~