Опишите алгоритм для нахождения миллиона наименьших чисел в наборе из миллиарда чисел. Память компьютера позволяет хранить весь миллиард чисел

Существует много способов решить эту задачу. Мы остановимся только на трех — сортировка, минимум кучи и ранжирование.

Решение 1. Сортировка

Можно отсортировать элементы в порядке возрастания, а затем взять первый миллион чисел. Это потребует O(n log(n)) времени.

Решение 2. Минимум кучи

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

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

В итоге мы получим кучу, содержащую миллион наименьших чисел. Эффективность алгоритма O(n log(m)), где m — количество значений, которые нужно найти.

Решение 3. Ранжирование (если изменять исходный массив)

Данный алгоритм очень популярен и позволяет найти i-й наименьший (или наибольший) элемент в массиве.

Если элементы уникальны, поиск i-гo наименьшего элемента потребует О(n) времени. Основной алгоритм будет таким:

1. Выберите случайный элемент в массиве и используйте его в качестве «центра». Разбейте элементы вокруг центра, отслеживая число элементов слева.
2. Если слева находится ровно i элементов, вам нужно вернуть наибольший элемент.
3. Если слева находится больше элементов, чем i, то повторите алгоритм, но только для левой части массива.
4. Если элементов слева меньше, чем i, то повторите алгоритм справа, но ищите алгоритм с рангом i - leftSize.

Приведенный далее код реализует этот алгоритм.

			public int partition(int[] array, int left, int right, int pivot) {
	while (true) {
		while (left <= right && array[left] <= pivot) {
			left++;
		}
	
		while (left <= right && array[right] > pivot) {
			right--;
		}

		if (left > right) {
			return left - 1;
		}

		swap(array, left, right);
	}
}

public int rank(int[] array, int left, int right, int rank) {
	int pivot = array[randomIntInRange(left, right)];
	
	/* Раздел и возврат конца левого раздела */
	int leftEnd = partition(array, left, right, pivot);
	
	int leftSize = leftEnd - left + 1;
	if (leftSize == rank + 1) {
		return max(array, left, leftEnd);
	} else if (rank < leftSize) {
		return rank(array, left, leftEnd, rank);
	} else {
		return rank(array, leftEnd + 1, right, rank - leftSize);
	}
}
		

Как только найден наименьший i-й элемент, можно пройтись по массиву и найти все значения, которые меньше или равны этому элементу.

Если элементы повторяются (вряд ли они будут «уникальными»), можно слегка модифицировать алгоритм, чтобы он соответствовал этому условию. Но в этом случае невозможно будет предсказать время его выполнения.

Существует алгоритм, гарантирующий, что мы найдем наименьший i-й элемент за линейное время, независимо от «уникальности» элементов. Однако эта задача несколько сложнее. Если вас заинтересовала эта тема, этот алгоритм приведен в книге Т. Кормен, Ч. Лейзер-сон, Р. Ривестп, К. Штайн «CLRS’ Introduction to Algorithms».

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».