配列の操作（最小限の削除が必要）

Question

正の整数の配列が与えられた場合、残りのすべての非ゼロ要素が等しいように任意の要素を任意の量だけ減らすことができます。

私はすべての減少の合計である最小値を見つける必要があります。

EX：1 1 1 1 2
Ans：1（最後の要素のみを1減らす）。

EX：25 23 1 2
Ans：5（可能な方法は25から23を減らし、1から0に減らし、2から0に減らすことです）すべての減少操作配列が23 23 0 0 0以外の要素が等しい）

私は配列の最小値を見つけて、他のすべての要素をそれと等しくする方法を試しました。しかし、そのアプローチは、2番目のケースで失敗します。これについての助けは非常に高く評価されます。

Answer 1

あなたのアプローチは良いですが、目標値の選択肢を増やす必要があります。

これは配列内の値のいずれかである可能性があります。したがって、すべてを順番に試してみてください。これはO（n^2）アルゴリズムになります。

もっと速くしたい場合は、最初にエントリを並べ替えることができます。次に、各目標値のコストを簡単に計算することができます（現在の位置が0になる前にすべての要素を減らし、現在の位置の後にあるすべての要素を目標値に減らす必要があることが分かっているため、合計コストはすべての要素から現在の値から現在の位置を超えた要素の数を引いたもの）

Answer 2

あなたのアプローチは良いと思うが、大きな落とし穴があり、常にうまくいかない。番号をゼロに一致させるオプションがない場合は機能します。この問題のシナリオでは、各候補について、より大きい数値をすべてこの候補に等しくし、すべての小さな数値をゼロに等しくして得た差の合計を計算し、どの候補が最小の差異の合計を持つかを調べる必要があります。配列は負の数を持っている場合は、エラーを投げるか、-1を返し（エラーコード）：ここ

はアルゴ...

1. ベースケースです。
2. 分類：ソート配列 - O（N Nログ）
3. 左合計：左から右へ、各位置については、左側のすべての数の累積合計を計算します。 - O（n）
4. 右の合計：右から左へ、各位置について、右のすべての要素の累積合計を計算します。 - O（n）
5. 最小の相違点：各位置について、ゼロ以外のすべての要素と等しい最小の数と仮定します。小さい数字はすべてゼロに減らす必要があります。したがって、この位置に対応する左の合計を取る。大きい数字はすべてこの数値に減らす必要があります。したがって、超過分を計算し、それを左の合計に加算します。結果の合計が現在の最小値よりも小さい場合は、現在の最小値を更新します。 - O（n）の

全体の複雑さがO（nは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; 
}