Массирование массива (требуется минимальное удаление)

Question

Учитывая массив на положительных целых числах, я могу уменьшить любой элемент на любую сумму, чтобы все остальные ненулевые элементы были равны.

Мне нужно найти минимальное значение, которое является суммой всего уменьшения.

EX: 1 1 1 1 2
Ans: 1 (уменьшение только последнего элемента на 1).

ЕХ: 25 23 1 2
Ans: 5 (один из возможных способов состоит в уменьшении 25 до 23, и уменьшение от 1 до 0, уменьшение 2 до 0 После того, как все уменьшение операции массива 23 23 0 0, который имеет все. ненулевой элемент равен.)

Я попытался найти минимальное значение в массиве и затем приравнивать все остальные элементы к этому. Но этот подход не оправдывает второй случай. Любая помощь по этому поводу высоко ценится.

Answer 1

Ваш подход хорош, но вам нужно рассмотреть дополнительные варианты для целевого значения.

Это может быть любое из значений в массиве, поэтому просто попробуйте все по очереди. Это будет алгоритм O (n^2).

Если вы хотите ехать быстрее, вы можете отсортировать записи в первую очередь. Затем вы можете легко вычислить стоимость каждого целевого значения по очереди (потому что вы знаете, что вам нужно уменьшить все элементы до текущей позиции до 0 и все элементы после текущей позиции до целевого значения, поэтому общая стоимость представляет собой сумму все элементы минус текущее значение умножает количество элементов за пределы текущей позиции)

Answer 2

Ваш подход звучит неплохо, но имеет серьезные подводные камни, и он не работает все время. Он будет работать, если нет возможности приравнивать число к нулю. В этом проблемном сценарии для каждого кандидата вы должны рассчитать сумму различий, полученную путем приравнивания всех больших чисел к этому кандидату и всех меньших чисел до нуля, и посмотрите, какой кандидат имеет наименьшую сумму различий.

Вот алго ...

1. Базовый вариант: Если массив имеет отрицательное число, выдаст ошибку или возвращает -1 (код ошибки).
2. Сортировка: Сортировка массива - O (п § п)
3. слева Сумма: Слева направо, для каждой позиции вычислить накопленную сумму всех чисел на левой. - O (n)
4. Право Сумма: Справа налево, для каждой позиции вычисляют совокупную сумму всех элементов справа. - O (n)
5. Минимальная разница: Для каждой позиции предположим, что это минимальное число, на которое вы приравниваете все ненулевые элементы. Все меньшие числа должны быть сведены к нулю. Итак, возьмите левую сумму, соответствующую этой позиции. Все большее число должно быть уменьшено до этого числа. Итак, вычислите, что такое избыток, и добавьте его в левую сумму. Если итоговая сумма меньше текущего минимума, обновите текущий минимум.- О (п)

Общая сложность O (п журнал п) и вот какой-то код ...

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; 
}