тема
Введите n целых чисел и найдите среди них наименьшее число K. Например, если вы введете 8 цифр 4,5,1,6,2,7,3,8, самые маленькие 4 цифры будут 1,2,3,4.
Разобрать
идея первая
Очевидно, что самый простой ответ — отсортировать исходный массив и просто взять первое k.
Примечание. Это можно разделить на ситуации:
- Если k намного меньше n, можно использовать пузырьковый алгоритм или алгоритм выбора для выбора наименьшего значения в текущей последовательности, сложность которого составляет O (nk).
- Если k ненамного меньше n, то лучше выбрать алгоритм O(nlogn)
/**
* 排序的做法
* @param input
* @param k
* @return
*/
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if(input == null || k <= 0 || k > input.length) {
return result;
}
Arrays.sort(input);
for(int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
}
идея вторая
Мы заметили, что задача не требует упорядочения минимального количества выходов k, поэтому мы можем использовать идею функции распределения в быстрой сортировке для решения задачи. Потому что partion может сделать последовательность разделенной на две части: все значения слева меньше дозорного, а значения справа все больше дозорного. Таким образом, нам нужно только найти дозорный в k-м положении, то есть найти положение, в котором находится k-е наибольшее значение, тогда значение k-1 слева от него меньше или равно k-му наибольшему значению. Очевидно, что первые k значений — это минимальные k чисел, которые мы ищем. В нашем процессе деления есть 3 случая:
- Позиция часового больше, чем k, что указывает на то, что k-е наибольшее число находится слева, и левая часть может быть обработана рекурсивно.
- Позиция часового меньше k, что указывает на то, что K-е наибольшее число находится справа, и этого достаточно для продолжения рекурсивной обработки.
- Позиция дозорного равна k, что указывает на то, что дозорный является K-м наибольшим значением, а k-1 чисел слева меньше или равны ему, поэтому первый вывод k является желаемым результатом.
/**
* 基于快排的划分函数的思想来做的。
* @param input
* @param k
* @return
*/
public static ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if(input == null || k <= 0 || k > input.length) {
return result;
}
findKthValue(input, 0, input.length - 1, k - 1);
for(int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
}
public static void findKthValue(int[] input, int low, int high, int k) {
if(low < high) {
int pivot = new Random().nextInt(high - low + 1) + low;
swap(input, pivot, high);
int index = low;
for(int i = low; i < high; i++) {
if(input[i] < input[high]) {
swap(input, i, index);
index++;
}
}
swap(input, index, high);
if(index > k) {
findKthValue(input, low, index - 1, k);
}else if(index < k) {
findKthValue(input, index + 1, high, k);
}
}
}
Идея 3
это типичноПроблема Топ-К, то есть задача нахождения наименьшего числа k или наибольшего числа k из n чисел.
Обычно мы используем контейнер емкостью k для хранения k наименьших значений. Нам нужно только один раз пройти по исходному массиву, чтобы получить наименьшее число k.
- Сначала контейнер пуст, когда количество пройденных чисел меньше вместимости k контейнера, значение сразу добавляется в контейнер.
- Когда емкость контейнера заполнена, оцените, превышает ли максимальное значение в контейнере точку, которую нужно вставить:
- Если оно больше, удалите максимальное значение из контейнера и добавьте точку для вставки.
- Если оно меньше или равно, ничего не делать и продолжать переход к следующему значению.
Вопрос превращается в то, как эффективно получить максимальное значение в контейнере.Элегантная структура данных отлично решает эту проблему, а именно структуру кучи, которая делится на большую корневую кучу или маленькую корневую кучу. Очевидно, здесь следует выбратьбольшая куча корней. В большой корневой куче корневой узел больше, чем все точки в левом поддереве и правом поддереве, поэтому нам нужно только посетить корневой узел, чтобы получить максимальное значение емкости k, а структура данных может динамически регулировать структура кучи для вставленного значения, так что встречайте большую корневую кучу. По поводу конкретного кода кучи я в будущем напишу отдельный блог, и повторяться здесь не буду.
В Java нет специального результата данных кучи, но есть очередь с приоритетом, основанная на структуре кучи, поэтому здесь мы используем очередь с приоритетом и настраиваем компаратор для удовлетворения потребностей большой корневой кучи.
/**
* Topk问题
* @param input
* @param k
* @return
*/
public static ArrayList<Integer> GetLeastNumbers_Solution3(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if(input == null || k <= 0 || k > input.length) {
return result;
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
//因为要满足大根堆需求，所以使用自定义比较器，比较策略为o1大于o2时，o1放o2的前面
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for(int i = 0; i < input.length; i++) {
if(i < k) {
priorityQueue.add(input[i]);
} else if(input[i] < priorityQueue.peek()) {
priorityQueue.poll();
priorityQueue.add(input[i]);
}
}
result.addAll(priorityQueue);
return result;
}
Суммировать
Комбинируйте алгоритмы сортировки и общие структуры данных, чтобы упростить задачи.
Статья включена в [личную колонку (обновление)](https://blog.csdn.net/column/details/23876.html), и я с нетерпением жду ответа на общие вопросы интервью с вами.