我在面試中被問到一個編碼問題，描述如下 N個工廠正在產生污染。以整數形式給定污染量。迷你數。不。將總污染減少至少一半所需的過濾器。一個過濾器可將污染減少一半。如果您在同一工廠放置另一個過濾器，它將是第 4 個（N/2/2）
Example: N =[5,19,8,1]
totalPollution = 5 19 8 1=33
numberOfFiltersRequire =3
因為我們可以這樣做 = [(19/2)/2, 8/2,5,1] = 4.75 4 5 1 = 14.75 這還不到現有污染的一半
Example: N =[3,0,5]
numberOfFiltersRequire =2
因為我們需要為此在兩個污染工廠中放置過濾器， 所以我撰寫了如下代碼
int solve(int[] n){
int count = 0;
int totalPollution = Arrays.stream(n).sum();
int halfPollution = totalPollution/2; //I know I should have taken double but thought int wold work
long distinct = Arrays.stream(n).distinct)().count();
if(distinct == 1l)
return n; // this is the corner case where all factories pollute equally i.e [10,10]
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int a:n)
pq.add(a);
while(totalPollution >= halfPollution){
int currnetPoll = pq.poll();
int halfVal = currentPoll/2;
totalPollution -= halfVal;
count ;
pq.add(halfVal);
}
return count;
}
但對我來說很奇怪，它只通過了示例測驗用例，但沒有為我通過任何其他測驗用例，誰能幫助我如何改進？
uj5u.com熱心網友回復：
您的編程邏輯似乎沒問題。是貪心演算法。使用優先佇列，每次洗掉最大的元素將其減半并添加回優先佇列。看起來你錯過了這個：
迷你數。不。將總污染減少至少一半所需的過濾器。
然后跟隨是錯誤的。
while(totalPollution >= halfPollution)
它一定要是
while(totalPollution > halfPollution)
uj5u.com熱心網友回復：
您可以按降序對陣列進行排序，然后將每個值除以 2，直到它低于下一個值，每次除法時遞增計數器。像這樣的東西：
int solve(int[] n){
int[] sortedArr = Arrays.stream(n).boxed().sorted(Comparator.reverseOrder())
.mapToInt(Integer::intValue).toArray();
if(sortedArr.length == 1)
return 1;
double prevNum = sortedArr[0];
int total = Arrays.stream(sortedArr).sum();
double requiredValue = (double) total/(double) 2;
int countFilter = 0;
for(int i=1; i<sortedArr.length; i ){
while (prevNum >= sortedArr[i] && total>requiredValue){
//System.out.println(prevNum " " n[i] " " total " " countFilter);
prevNum=prevNum/(double) 2;
total-=prevNum;
countFilter ;
}
}
return countFilter;
}
uj5u.com熱心網友回復：
貪心演算法會起作用，但我會提到你也可以解決這個問題O(n)，而無需太多額外的努力。這個想法是根據它們的最高設定位將元素拆分arr為“桶”，并一次對整個最高位桶進行操作。最后一步是一個基于快速選擇的演算法，它模仿貪心演算法，但允許我們避免排序。
m根據元素的最高設定位將元素劃分為桶（因此1 ceiling(log_2(max(arr)))最多桶。對于每個桶，還存盤其總和及其包含的元素數。- 保留一個
total_reduction_still_needed變數，初始化為sum(arr)/2. 還要保留一個filters_used變數，初始化為0. 由于我們所有的元素即使在除以 之后也可以表示為二進制分數2，因此您甚至可以算術左移所有整數，m 1以避免必須使用浮點數學，但這并不是絕對必要的。 - 雖然我們最高桶的總和
B除以 2 小于或等于：將tototal_reduction_still_needed的成員數相加，從仍然需要的減少中減去，并將 的所有元素移動到第二高的桶，更新其總和和數數。Bfilters_usedsum(B)/2B - 現在，我們有一個最高的桶
B，其總和是仍然需要減少的兩倍以上。我們需要從桶中找到最少數量的元素，這些元素的總和至少為給定數量。O(n)我們可以使用快速選擇 中位數的中位數和額外的簿記來及時完成此操作，而不是排序。這是一種比較常見的技術，但需要更長的時間來解釋；例如，參見給出偽代碼和解釋的這個執行緒。
唯一需要O(n)時間證明的部分是（3）中的“將元素移動到下一個最高桶”步驟。但是，請注意，從一開始就在每個工廠上放置兩個過濾器會給出所需過濾器總數的上限，因此我們最多2n只在此處進行元素移動（有更好的上限，但這就是證明所需要的全部） .
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424327.html