數組操作（需要最小刪除）

Question

給定一個正整數數組，我可以減少任何元素的數量，使得所有其餘的非零元素相等。

我必須找到所有減少發生的總和的最小值。

EX：1 1 1 1 2
Ans：1（僅減少最後一個元素1）。

EX：25 23 1 2
答案：5（一種可能的方法是減少25到23，減少1到0，減少2到0，所有減少操作之後數組是23 23 0 0，非零元素相等）

我試着找到數組中最小的方法，然後將所有其他元素等同於此。但是，這種方法失敗了第二種情況。任何幫助，這是高度讚賞。

Answer 1

您的方法很好，但您需要考慮更多的目標值選擇。

它可能是數組中的任何值，因此只需依次嘗試所有這些值。這將是一個O（n^2）算法。

如果您想要加快速度，您可以先排序條目。然後，您可以依次輕鬆地計算每個目標值的成本（因爲您知道需要將當前位置之前的所有元素減少到0，並且將當前位置之後的所有元素減少到目標值，因此總成本是總和所有元素減去當前值乘以當前位置以外的元素的數量）

Answer 2

您的方法聽起來不錯，但有重大缺陷，並且它一直無法工作。如果沒有選項將數字等於零，它將起作用。在這個問題場景中，對於每個候選人，您應計算將所有較大數字等同於此候選人並將所有較小數字均等於零而獲得的差異總和，並查看哪個候選人具有最小差異總和。

這裏的算法中......

1. 基本情況：如果數組有負數，拋出一個錯誤或返回-1（錯誤代碼）。
2. 排序：排序的陣列 - 爲O（n log n）的
3. 左總：從左至右，每個位置計算左邊的所有數字的累計總和。 - O（n）
4. 右總和：從右到左，每個位置計算右側所有元素的累計總和。 - O（n）
5. 最小差異：對於每個位置，假設這是將所有非零元素等同於的最小數。所有較小的數字應該減少到零。所以，拿這個位置的左邊和。所有較大的數字應該減少到這個數字。所以，計算什麼是多餘的，並將其添加到左邊的總和。如果總和小於當前最小值，則更新當前最小值。 - 爲O（n）

整體複雜度爲爲O（n log n）的和這裏的一些代碼...

private static int getMinimumDifference(int[] arr) { 
    int n = arr.length; 

    for (int i = 0; i < n; i++) { 
     if (arr[i] < 0) { 
      return -1; 
     } 
    } 
    if (n == 1) 
     return 0; 

    int left[] = new int[n]; 
    int right[] = new int[n]; 

    Arrays.sort(arr); 

    int tempSum = 0; 
    for (int i = 0; i < n; i++) { 
     left[i] = tempSum; 
     tempSum += arr[i]; 
    } 

    tempSum = 0; 
    for (int i = n - 1; i >= 0; i--) { 
     right[i] = tempSum; 
     tempSum += arr[i]; 
    } 

    int minDiff = tempSum, index = -1; 
    for (int i = 0; i < n; i++) { 
     int diff = 0; 
     diff += left[i]; // All numbers on the left reduced to 0 
     diff += right[i] - (arr[i] * (n - i - 1)); // All numbers on the right reduced to arr[i] 
     if (diff < minDiff) { 
      minDiff = diff; 
      index = i; 
     } 
    } 
    System.out.println("Minimum difference is " + minDiff + " and all numbers should be " + (index >= 0 ? arr[index] : "unknown")); 
    return minDiff; 
}