Наименьшее количество различных целых чисел после K удалений

Дан массив целых чисел arr и целое число k.

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

Входные данные:

• размер массива от 1 до 10000
• элементы массива натуральные числа от 1 до 10^9
• K - от 0 до arr.Length.

Примеры:

1. arr = [5,5,4], k = 1
Output: 1

2. arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Пояснение: удаляем 4, 2 и например 1, тогда останутся 3, 1, 3, 3, т.е. останутся 2 уникальных целых числа 1 и 3.

Разбор

Формулировка задачи не совсем понятна, на что справедливо указали в комментариях к этой задачи. Тут необходимо так удалить K элементов массива, что на выходе получится наименьшее количество "уникальных" различных целых чисел.

Для наглядности можно еще раз разобрать 2й пример задачи. Тогда решение будет довольно очевидным.

Алгоритм

1. Ключом к решению будет словарик, где ключом будет элемент массива, а значением - количество его вхождений в массив.
2. 2м шагом будет сортировка словарика по значению таким образом, что элементы с наименьшим количеством вхождений в массив будут вначале.
3. Далее мы проходим по полученному списку количества вхождений элементов и вычитаем исходное число K. Считаем количество итераций, которые нам понадобятся.
4. Тогда ответом будет разность размера списка и этого счетчика, т.е. количество уникальных / различных целых чисел после удаления K элементов.

Реализация

public static int FindMinNumOfUniqueIntegers(int[] arr, int k) {
	var map = new Dictionary<int, int>();
	for (int i = 0; i < arr.Length; i++)
	{
	    if (!map.ContainsKey(arr[i]))
	    {
		map[arr[i]] = 0;
	    }
	    map[arr[i]] += 1;
	}

	int count = 0;
	var sortedFreq = map.OrderBy(x => x.Value).Select(x => x.Value);
	foreach (int freq in sortedFreq)
	{
	    if (freq > k)
	    {
		break;
	    }

	    k -= freq;
	    count++;
	}

	return sortedFreq.Count() - count;
}

https://gist.github.com/unilecs/44954a4bb4fc6c75711a2de690d1b240

Play-test

https://dotnetfiddle.net/Sije7v