這個問題在面試中被問到。我仍然無法找到嘗試這個問題的正確方法。
給定一個陣列 = [7,2,2] 找到使陣列元素幾乎相等所需的最小傳輸次數。如果這是不可能的，較大的元素應該出現在左側。
在上面的例子中，陣列的最終狀態是 [4,4,3]，答案是 2 1 =3。我們將 2 從 7 轉移到第一個 2，然后我們將另一個 1 從 7 轉移到 2。
如果輸入是 [2,2,7]，那么答案將是 4，因為我們需要在左側保留更大的元素。final state = [4,4,3] 2 從 7 轉移到兩個 2 使最終計數為 4。
uj5u.com熱心網友回復：
一次完成 1 個單位的最小傳輸量是輸入與所需陣列的差異總量的一半。根據您提供的內容，“幾乎相等”似乎并不意味著任何復雜化。
uj5u.com熱心網友回復：
解決方案是想象目標陣列是什么。此目標陣列將僅取決于原始陣列中值的總和以及陣列的長度（顯然必須保持不變）。
如果值的總和是陣列長度的倍數，則目標陣列中的所有值都將相同。但是，如果存在余數，則該余數表示將比陣列末尾的某些值多 1 的陣列值的數量。
我們實際上不必存盤該目標陣列。它由商和總和除以陣列長度的余數隱式定義。
該函式的輸出是與實際輸入陣列值和任何陣列索引處的預期值的差異之和。我們應該只計算正差異（即從一個值中轉移），否則我們會計算兩次轉移——一次在傳出端，一次在傳入端。
這是一個基本的 JavaScript 實作：
function solve(arr) {
// Sum all array values
let sum = 0;
for (let i = 0; i < arr.length; i ) {
sum = arr[i];
}
// Get the integer quotient and remainder
let quotient = Math.floor(sum / arr.length);
let remainder = sum % arr.length;
// Determine the target value until the remainder is completely consumed:
let expected = quotient 1;
// Collect all the positive differences with the expected value
let result = 0;
for (let i = 0; i < arr.length; i ) {
// If we have consumed the remainder, reduce the expected value
if (i == remainder) {
expected = quotient;
}
let transfer = arr[i] - expected;
// Only account for positive transfers to avoid double counting
if (transfer > 0) {
result = transfer;
}
}
return result;
}
let array = [7,2,2];
console.log(solve(array)); // 6uj5u.com熱心網友回復：
讓我們從目標陣列開始。它是什么？
有了{7, 2, 2}我們想要獲得{4, 4, 3}. 所以每個專案至少是3，一些頂級專案是3 1 == 4。該演算法是
let sum = sum(original)
let rem = sum(original) % length(original) # here % stands for remainder
target[i] = sum / length(original) (i < rem ? 1 : 0)
擁有original和target
original: 7 2 2
target: 4 4 3
transfer: 3 2 1 (6 in total)
注意
transfer[i]只是一個絕對的區別：abs(original[i] - target[i])- 我們計算每個
transfer兩次：一次我們減去，然后我們加上。
所以答案是
sum(transfer[i]) / 2 == sum(abs(original[i] - target[i])) / 2
代碼（C#）：
private static int Solve(int[] initial) {
// Don't forget about degenerated cases
if (initial is null || initial.Length <= 0)
return 0;
int sum = initial.Sum();
int rem = sum % initial.Length;
int result = 0;
for (int i = 0; i < initial.Length; i)
result = Math.Abs(sum / initial.Length ((i < rem) ? 1 : 0) - initial[i]);
return result / 2;
}
演示：（小提琴）
int[][] tests = new int[][] {
new int[] {7, 2, 2},
new int[] {2, 2, 7},
new int[] {},
new int[] {2, 2, 2},
new int[] {1, 2, 3},
};
string report = string.Join(Environment.NewLine, tests
.Select(test => $"[{string.Join(", ", test)}] => {Solve(test)}"));
Console.Write(report);
結果：
[7, 2, 2] => 3
[2, 2, 7] => 4
[] => 0
[2, 2, 2] => 0
[1, 2, 3] => 1
uj5u.com熱心網友回復：
在我看來，這是一個可以通過greedy方法解決的簡單問題。
腳步：
- 總結
input陣列元素S，除以它的長度n。比方說，商是Q，余數（mod）是R。然后，最終陣列target將具有1st R elements with value = Q 1. 其余元素將是Q. - 傳輸次數將是
input and target陣列中每個（相應）位置的絕對差之和的一半。
例子：
Input [7, 2, 2]
S=11 n=3 Q=11/3=3 R=11%3=2
Target [3 1, 3 1, 3]
Answer = (abs(7-4) abs(2-4) abs(2-3)) / 2 = 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400703.html
上一篇：最大公分母演算法背后的邏輯
下一篇：Android：基于迭代佇列的洪水填充演算法“expandToNeighborsWithMap()”函式例外緩慢