Равные элементы в массиве - PullRequest
Новая
       3

Равные элементы в массиве

3 голосов
/ 27 марта 2020

Сегодня у меня было Интервью, где мне задали одну проблему, и я даже не мог понять.

Задача:

Дана одна array ?, состоящая из ? целых чисел.

Получите не менее ? равных элементов в array ?.

. При расчете можно выполнить следующие две операции:

  • Взять один из минимальных элементов. массива и увеличьте его значение на единицу (более формально, если минимальное значение ? равно ??, тогда вы выбираете такой индекс ?, что ?? = ?? и задаете ??: = ?? + 1);

  • взять один из максимальных элементов массива и уменьшить его значение на единицу (более формально, если максимальное значение ? равно ??, тогда вы выбираете такой индекс ?, что ?? = ?? и задаете ??: = ?? − 1).

Рассчитайте минимальное количество ходов, необходимое для получения не менее ? равных элементов в массиве.

Может кто-нибудь помочь мне понять, что такое актуальная проблема о т, чтобы я мог написать код?

Ответы [ 2 ]

6 голосов
/ 27 марта 2020

Чтобы ответить на ваш вопрос напрямую: «Помогите мне понять проблему»:

Например, вот ваш массив: 

{1,2,5,7,8,3}

Теперь вы можете выполнять только эти две операции :

  1. Найдите минимальный элемент и увеличьте его: 
{2,2,5,7,8,3} // <-- increased 1
Уменьшите максимальный элемент: 
{2,2,5,7,7,3} // <-- decreased 8

И теперь возникает вопрос: каково минимальное число ходов, чтобы этот массив содержал k идентичных чисел?

Так что если k = 3 и массив такой же, как указано выше, то одним из решений будет запуск операции 1 три раза:

  1. Перед любыми шагами: 
{1,2,5,7,8,3}
После первого хода: 
{2,2,5,7,8,3} // <-- `1` changed to `2`
После второго хода: 
{3,2,5,7,8,3} // <-- `2` changed to `3`
После третьего хода: 
{3,3,5,7,8,3} // <-- `2` changed to `3`

Таким образом, результирующий массив будет иметь вид: 

{3,3,5,7,8,3}

Вы понимаете проблему сейчас?

4 голосов
/ 27 марта 2020

С точки зрения алгоритма, чтобы найти k равных элементов:

На любом данном шаге в алгоритме есть некоторое количество равных элементов, скажем, j. Если j >= k, все готово. В противном случае вам нужно выбрать какую-то комбинацию ходов, чтобы увеличить j.

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

Допустим, существует уникальный максимальный элемент (т. Е. Когда в массиве есть только один элемент, равный максимальному элементу). Вы можете увеличить j (как минимум) на 1, уменьшив его до тех пор, пока он не станет равным второму по величине элементу.

Аналогичным образом, вы можете увеличить j (как минимум) на 1, увеличив уникальный уникальный минимальный элемент (т. е. когда в массиве есть только один элемент, равный максимальному элементу), пока он не станет равным второму наименьшему элементу.

Следовательно, наименьшее число ходов для достижения (как минимум) 1 увеличения равно один из [уменьшить максимум; увеличить максимальное значение], которое достигает этого.

Например, в массиве [1, 3, 5, 6] вы можете выбрать:

  • Сделайте 2 шага, чтобы увеличить 1, чтобы он равнялся 3: [3, 3, 5, 6]
  • Сделайте 1 ход, чтобы уменьшить 6, чтобы оно равнялось 5: [1, 3, 5, 5]

В этом случае вы увеличиваете j на 2 наиболее дешево, уменьшая значение 6.

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

( Аналогично для минимальных элементов)

Итак, ваш алгоритм может найти (жадное) минимальное количество шагов, чтобы сделать j == k, решив, [уменьшить максимальные элементы] или [увеличить минимальный элемент]. Я не знаю, является ли жадный минимум на самом деле минимумом, но я не могу придумать очевидного алгоритма, чтобы найти его без жадности, кроме поиска всех возможностей, которые имели бы ужасную вычислительную сложность, так что, вероятно, не то, что это интервью искал.

...