leetcode164. Maximum Gap

張利勇發布于2019-08-15 14:18 / 2826人閱讀

摘要：這里最小的意思并不是說任意兩個數之間的最小間隔，而是指這一組數字的最大間隔必然不小于這個最小間隔。而每個桶內的數字間隔必然不會超過最小間隔。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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