Блог

Этот вопрос взят из этой ссылки.Учитывая непустой массив целых чисел размером n, найдите минимальное количество ходов, необходимых для того, чтобы все элементы массива стали равными, где ход увеличивает n — 1 элементов на 1.

 Example:

Input:
[1,2,3]

Output:
3
  

Объяснение:

 Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
  

Ссылки ниже содержат рабочее решение:

 class Solution {
    public int minMoves(int[] nums) {
       int total=0, least=numbers[0];
        for (int i = 0; i < numbers.length; i  ) {
            if (numbers[i] < least) {
                least = numbers[i];
            }
            total = total   numbers[i];
        }
        return total - least * numbers.length; 
    }
}
  

Здесь least — минимальное значение из массива, а total — сумма всех элементов из массива.

Но мне интересно, как значение total - least * numbers.length решает эту проблему. что это за формула? может кто-нибудь, пожалуйста, объяснить?

‘Увеличение n — 1 элементов на 1’ равно ‘уменьшению 1 элемента на 1 (и увеличению каждого элемента, но это не имеет никакого смысла)’.

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

Итак, сначала вы должны найти минимальное значение из массива, а затем получить сумму всех элементов и вычесть минимальное количество элементов, умноженное на количество элементов.

Ну, если рассматривать с точки зрения «по модулю», увеличение n-1 элементов массива было бы таким же, как уменьшение одного значения массива (в контексте этой проблемы). Например, если вы увеличите первые 3 элемента из [1; 1; 1;2] до [2;2;2;2], это будет точно так же, как уменьшение последнего элемента: [1;1;1;2] становится [1;1;1;1], которое удовлетворяет условию задачи.

Итак, проблема становится немного проще для понимания: при каждом перемещении вы можете уменьшать размер одного элемента. Итак, вам нужно уменьшить количество всех элементов из списка, пока они не станут равны минимальному элементу списка. Затем количество ходов становится S - length * min таким, что вам пришлось бы уменьшить S раз, чтобы привести все элементы к 0, но вы могли бы сэкономить несколько ходов, достигнув массива, имеющего только минимальное значение ( length * min )

 // We have number 123
// Algorythm is simple: (add all digits to each other)
// and substract (smallest digit * quantity of digits)
let moves = (1   2   3) - (1*3);
console.log(moves);

// 622
moves = (6   2   2) - (2*3);
console.log(moves);

// 183
moves = (1   8   3) - (1*3);
console.log(moves);  

Итак, мы можем написать простую функцию для вычисления ходов для чисел

 // Moves function
const getMoves = (num) => {
  // Get summ of all digits
  const sum = String(num).split('').reduce((a, c) => Number(a)   Number(c));
  // Get minimum digit
  const min = String(num).split('').reduce((a, c) => a > c ? c : a);
  // Get number length
  const nl = String(num).length;
  // Calculate and return moves
  return sum - (min * nl);
};

// Test
console.log(getMoves(123));
console.log(getMoves(622));
console.log(getMoves(183));  

И, наконец, напишите альтернативу вашей функции для работы с массивами

 // Moves function
const getMoves = (arr) => {
  const sum = arr.reduce((a, c) => a   c);
  const min = arr.reduce((a, c) => a > c ? c : a);
  return sum - (min * arr.length);
};

// Test
console.log(getMoves([1,2,3]));
console.log(getMoves([6,2,2]));
console.log(getMoves([1,8,3]));  

Я думал о формуле —

 number of moves = sum total - least * numbers.length
  

Вот как я пытался это понять. Допустим, у нас есть 3 числа — a, b, c. Минимальное из этих чисел равно a . Теперь мы можем записать сумму этих чисел следующим образом —

 Sum Total = a   b   c = 3a   (b - a)   (c - a)
  

Общее количество ходов должно быть суммой разности между другими числами. Итак, формула становится —

 Sum Total = 3a   number of moves
  

Таким образом, получается —

 number of moves = Sum Total - 3a