資訊專欄INFORMATION COLUMN
摘要：這里最小的意思并不是說(shuō)任意兩個(gè)數(shù)之間的最小間隔，而是指這一組數(shù)字的最大間隔必然不小于這個(gè)最小間隔。而每個(gè)桶內(nèi)的數(shù)字間隔必然不會(huì)超過(guò)最小間隔。
題目要求
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ù)雜度來(lái)解決這個(gè)問(wèn)題。
思路和代碼這里并不需要完全的進(jìn)行排序。我們只需要找到合適的區(qū)間劃分，并將各個(gè)數(shù)字丟到其所屬的區(qū)間中。之后，我們只需要比較前一個(gè)區(qū)間的最大值和后一個(gè)區(qū)間的最小值之間的差距即可以獲得該數(shù)組最大的間隔。
這里選擇區(qū)間劃分的方式是找到這一組數(shù)字的“最小”間隔。這里最小的意思并不是說(shuō)任意兩個(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ì)超過(guò)最小間隔。所以正如上文所說(shuō)，比較相鄰兩個(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;
}
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/68528.html
摘要：這個(gè)的長(zhǎng)度是最小可能的最大差值。注意考慮和兩個(gè)邊界值也要加進(jìn)去。 題目：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...
摘要：題目鏈接題目分析給定一個(gè)數(shù)字，計(jì)算其二進(jìn)制表示中，出現(xiàn)的兩個(gè)最大距離。因?yàn)橹挥幸粋€(gè)是沒(méi)辦法比較距離的。當(dāng)出現(xiàn)時(shí)，判斷當(dāng)前距離是否大于記錄的最大值。最后判斷當(dāng)只有一個(gè)時(shí)，直接返回。否則返回所記錄的最大距離。 D47 868. Binary Gap 題目鏈接 868. Binary Gap 題目分析 給定一個(gè)數(shù)字，計(jì)算其二進(jìn)制表示中，出現(xiàn)的兩個(gè)1最大距離。 思路 當(dāng)然是先轉(zhuǎn)換成二進(jìn)制了。再...
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...
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...
LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹(shù)的最深深度。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 ...
閱讀 7248·2021-09-22 15:36
閱讀 6054·2021-09-02 10:20
閱讀 1936·2019-08-30 15:44
閱讀 2724·2019-08-29 14:06
閱讀 1218·2019-08-29 11:17
閱讀 1674·2019-08-26 14:05
閱讀 3238·2019-08-26 13:50
閱讀 1618·2019-08-26 10:26
