資訊專欄INFORMATION COLUMN
摘要：這個(gè)的長度是最小可能的最大差值。注意考慮和兩個(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 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.
解答：
這題挺難理解的，但是可以舉例，比如說現(xiàn)在有1, 3, 5, 9。那么我們可以把它分成3個(gè)bucket來裝，min表示在這個(gè)bucket范圍中，存在的最小數(shù)和最大數(shù)。這個(gè)bucket的長度是最小可能的最大差值。（如果哪個(gè)差值比這個(gè)還小，那么為了填補(bǔ)這個(gè)小差值，就必然存在另一個(gè)差值比它大，那么這個(gè)數(shù)組的最大差值就比當(dāng)前bucket大。所以均分下來的bucket是最小可能的最大差值）
b0: (1, 3) min = Integer.max, max = Integer.min
b1: (4, 6) min = Integer.max, max = Integer.min
b2: (7, 9) min = Integer.max, max = Integer.min
然后我們來看這個(gè)數(shù)組里的數(shù)在哪個(gè)bucket里，用(nums(i) - min) / gap來得到，
第一個(gè)數(shù)1在b0中，所以我們更新:
b0: (1, 3) min = 1, max = 1;
第二個(gè)數(shù)3在b0中，所以我們更新：
b0: (1, 3) min = 1, max = 3;
第三個(gè)數(shù)5在b1中，所以我們更新：
b1: (4, 6) min = 5, max = 5;
.
.
依次這樣下去。
因?yàn)槊總€(gè)bucket中的最大值－最小值就是我們最小的gap, 所以我們不用計(jì)算相鄰的兩個(gè)數(shù)，我們只要比較后一個(gè)bucket中的最小值和前一個(gè)bucket中的最大值相差多少，取最大相差的值就是最終的結(jié)果。注意考慮min和max兩個(gè)邊界值也要加進(jìn)去。
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) return 0;
int len = nums.length;
int max = nums[0], min = nums[0];
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
//Math.ceil與最小的比這個(gè)數(shù)大的蒸熟，使bucket可以包含所有數(shù)
int gap = (int)Math.ceil((double)(max - min) / (len - 1));
int[] BucketsMIN = new int[len - 1];
int[] BucketsMAX = new int[len - 1];
Arrays.fill(BucketsMIN, Integer.MAX_VALUE);
Arrays.fill(BucketsMAX, Integer.MIN_VALUE);
for (int num : nums) {
//不考慮邊界，所以把邊界的min和max都拿出來，多帶帶再考慮
if (num == min || num == max) continue;
int bucket = (num - min) / gap;
BucketsMIN[bucket] = Math.min(BucketsMIN[bucket], num);
BucketsMAX[bucket] = Math.max(BucketsMAX[bucket], num);
}
int result = 0;
int previous = min;
for (int i = 0; i < len - 1; i++) {
if (BucketsMIN[i] == Integer.MAX_VALUE && BucketsMAX[i] == Integer.MIN_VALUE) {
continue;
}
result = Math.max(result, BucketsMIN[i] - previous);
previous = BucketsMAX[i];
}
result = Math.max(result, max - previous);
return result;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64837.html
摘要：這里最小的意思并不是說任意兩個(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...
摘要：接下來說句聽起來很奇怪的話一個(gè)內(nèi)聯(lián)元素有兩個(gè)高度高度和實(shí)際區(qū)域高度是我自己發(fā)明的單詞，它表示對人類有效的高度，你在其他地方是看不到這個(gè)單詞的。你沒看錯(cuò)，是計(jì)算的一些細(xì)節(jié)對于內(nèi)聯(lián)元素，和會(huì)增大區(qū)域，但是不會(huì)增大不是的高度。 本文為饑人谷講師方方原創(chuàng)文章，首發(fā)于 前端學(xué)習(xí)指南。 這是一篇譯文，對 inline 和 inline-block 的元素剖析非常給力。 原文：Deep dive C...
摘要：插入兩條數(shù)據(jù)建立全文索引需要注意的是這里使用關(guān)鍵詞來代表全文索引，我們在這里就不建立數(shù)據(jù)模型了。全文索引查找表示要在全文索引中查東西。全文索引在工作還是經(jīng)常使用的，比如博客文章的搜索，長文件的關(guān)鍵詞搜索，這些都需要使用全文索引來進(jìn)行。 索引 在認(rèn)識(shí)索引的之前我們先建立一張表，并往其中插入200萬條數(shù)據(jù)。 // test.js //生成隨機(jī)數(shù) function GetRandomNum(...
摘要：全球云市場在年達(dá)到億美元增長放緩是自然的，但隨著新年的到來，繁榮將繼續(xù)推特，這標(biāo)志著評估行業(yè)格局的最佳時(shí)機(jī)。根據(jù)的最新報(bào)告，年全球云市場達(dá)到億美元億美元，年增長率為。此外，超尺度資本支出超過億美元，比年前三季度增長了。全球云市場在2018年達(dá)到2500億美元：增長放緩是自然的，但隨著新年的到來，繁榮將繼續(xù)推特，這標(biāo)志著評估行業(yè)格局的最佳時(shí)機(jī)。根據(jù)Synergy Research的最新報(bào)告，2...
閱讀 3443·2021-11-22 09:34
閱讀 1910·2019-08-30 12:53
閱讀 3505·2019-08-28 18:07
閱讀 2991·2019-08-27 10:55
閱讀 2969·2019-08-26 10:12
閱讀 3602·2019-08-23 18:21
閱讀 1352·2019-08-23 14:10
閱讀 1490·2019-08-23 13:04
