Алгоритм для нахождения k наименьших чисел в массиве из n элементов
Я пытаюсь написать алгоритм, который может печатать k наименьших чисел в n-size-массиве в O (n) времени, но я не могу уменьшить временную сложность до n. Как я могу это сделать?
Ответы
Ответ 1
Я сделал это в интервью раньше, и один из самых элегантных/эффективных способов сделать это -
O(n log k).
with space: O(k) (thanks, @Nzbuu)
В основном вы собираетесь использовать максимальную кучу размера, ограниченную k. Для каждого элемента массива проверьте, не меньше ли оно (только O (1)). Если это так, поместите это в кучу (O (log k)) и удалите макс. Если он больше, перейдите к следующему элементу.
Конечно, куча не дает отсортированного списка из k элементов, но это можно сделать в O (k log k), что легко.
Аналогично, вы можете сделать то же самое для поиска самых больших элементов k, и в этом случае вы будете использовать мини-кучу.
Ответ 2
вам нужно будет найти k'th наименьший элемент, используя "алгоритм выбора", который является O (n), а затем снова итерации массива и возврата каждого элемента, который меньше/равен ему.
Алгоритм выбора: http://en.wikipedia.org/wiki/Selection_algorithm
Вам нужно будет обратить внимание, если у вас есть повторы: вам нужно будет убедиться, что вы не возвращаете больше k элементов (это возможно, если, например, у вас есть 1,2,..., k, k, k,...)
РЕДАКТИРОВАТЬ:
Полный алгоритм и возврат списка в соответствии с запросом: пусть массив будет A
1. find the k'th element in A using 'selection algorithm', let it be 'z'
2. initialize an empty list 'L'
3. initialize counter<-0
4. for each element in A:
4.1. if element < z:
4.1.1. counter<-counter + 1 ; L.add(element)
5. for each element in A:
5.1. if element == z AND count < k:
5.1.1. counter<-counter + 1 ; L.add(element)
6. return L
обратите внимание, что требуется 3-я итерация, если в вашем списке могут быть дубликаты. если он не может - это бесполезно, просто измените условие в 4.1 на < =.
Также обратите внимание: L.add вставляет элемент в связанный список и, следовательно, O (1).
Ответ 3
Предполагая, что вы пытаетесь показать наименьшие числа K, вы можете использовать алгоритм Hoare Select, чтобы найти наименьшее число k th. Это разбивает массив на меньшие числа, число k th и большее число.
Ответ 4
Это можно сделать в ожидаемом линейном времени (O (n)). Сначала найдите наименьший элемент kth массива (используя метод разбиения на разделы для определения статистики порядка kth), а затем просто проведите по петле, чтобы проверить, какие элементы меньше наименьшего элемента kth. Обратите внимание, что это работает правильно только для отдельного элемента.
Вот код в c:
/*find the k smallest elements of an array in O(n) time. Using the Kth order
statistic-random pivoting algorithm to find the kth smallest element and then looping
through the array to find the elements smaller than kth smallest element.Assuming
distinct elements*/
#include <stdio.h>
#include <math.h>
#include <time.h>
#define SIZE 10
#define swap(X,Y) {int temp=X; X=Y; Y=temp;}
int partition(int array[], int start, int end)
{
if(start==end)
return start;
if(start>end)
return -1;
int pos=end+1,j;
for(j=start+1;j<=end;j++)
{
if(array[j]<=array[start] && pos!=end+1)
{
swap(array[j],array[pos]);
pos++;
}
else if(pos==end+1 && array[j]>array[start])
pos=j;
}
pos--;
swap(array[start], array[pos]);
return pos;
}
int order_statistic(int array[], int start, int end, int k)
{
if(start>end || (end-start+1)<k)
return -1; //return -1
int pivot=rand()%(end-start+1)+start, position, p;
swap(array[pivot], array[start]);
position=partition(array, start, end);
p=position;
position=position-start+1; //size of left partition
if(k==position)
return array[p];
else if(k<position)
return order_statistic(array, start,p-1,k);
else
return order_statistic(array,p+1,end,k-position);
}
void main()
{
srand((unsigned int)time(NULL));
int i, array[SIZE],k;
printf("Printing the array...\n");
for(i=0;i<SIZE;i++)
array[i]=abs(rand()%100), printf("%d ",array[i]);
printf("\n\nk=");
scanf("%d",&k);
int k_small=order_statistic(array,0,SIZE-1,k);
printf("\n\n");
if(k_small==-1)
{
printf("Not possible\n");
return ;
}
printf("\nk smallest elements...\n");
for(i=0;i<SIZE;i++)
{
if(array[i]<=k_small)
printf("%d ",array[i]);
}
}
Ответ 5
Можно найти k наименьшее из n элементов в O(n) времени (под которым я имею в виду true O(n) time, а не O(n + some function of k)). См. статью Википедии "Алгоритм выбора" , особенно подразделы "неупорядоченная частичная сортировка" и "медианный отбор как сводная стратегия", а также статью "Медиана медианов" для основной части, которая делает это O(n).
Ответ 6
Наилучшее возможное решение проблемы заключается в следующем. Используйте Quick sort, чтобы найти опорные точки и отбросить часть, где этот k-й элемент не лежит, и рекурсивно найти следующий опорный элемент. (Это kth Max finder, вам нужно изменить условие if else, чтобы сделать его kth Min Finder). Вот код JavaScript code-
// Complexity is O(n log(n))
var source = [9, 2, 7, 11, 1, 3, 14, 22];
var kthMax = function(minInd, MaxInd, kth) {
// pivotInd stores the pivot position
// for current iteration
var temp, pivotInd = minInd;
if (minInd >= MaxInd) {
return source[pivotInd];
}
for (var i = minInd; i < MaxInd; i++) {
//If an element is greater than chosen pivot (i.e. last element)
//Swap it with pivotPointer element. then increase ponter
if (source[i] > source[MaxInd]) {
temp = source[i];
source[i] = source[pivotInd];
source[pivotInd] = temp;
pivotInd++;
}
}
// we have found position for pivot elem.
// swap it to that position place .
temp = source[pivotInd];
source[pivotInd] = source[MaxInd];
source[MaxInd] = temp;
// Only try to sort the part in which kth index lies.
if (kth > pivotInd) {
return kthMax(pivotInd + 1, MaxInd, kth);
} else if (kth < pivotInd) {
return kthMax(minInd, pivotInd - 1, kth);
} else {
return source[pivotInd];
}
}
// last argument is kth-1 , so if give 2 it will give you,
// 3rd max which is 11
console.log(kthMax(0, source.length - 1, 2));
Ответ 7
Я знаю не совсем то, что вы ищете, но довольно простое O (n * k) время и пространство O (k). Это самая большая буква К, так что нужно будет ее провалить.
Для скота за мин k (результат) можно заменить кучей
private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
int[] result = new int[k];
int indexMin = 0;
result[indexMin] = testArray[0];
int min = result[indexMin];
for (int i = 1; i < testArray.Length; i++)
{
if(i < k)
{
result[i] = testArray[i];
if (result[i] < min)
{
min = result[i];
indexMin = i;
}
}
else if (testArray[i] > min)
{
result[indexMin] = testArray[i];
min = result[indexMin];
for (int r = 0; r < k; r++)
{
if (result[r] < min)
{
min = result[r];
indexMin = r;
}
}
}
}
return result;
}
Ответ 8
Другой метод - используйте QuickSelect Algorithm, и результатом будут все элементы слева от возвращаемого результата. Средняя временная сложность была бы O (n), а в худшем случае она была бы O (n ^ 2). Сложность пространства была бы O (1).
Ответ 9
Это может быть сделано за O (n) время, используя пространство O (n), как я полагаю. Как уже упоминалось, вы можете использовать алгоритм Hoares или вариант быстрого выбора.
По сути, вы запускаете Quicksort для массива, но запускаете только на той стороне раздела, которая необходима для того, чтобы обеспечить наличие элементов K или K-1 большего размера, чем сводная (вы можете либо включить lr, но исключить сводную). Если список не нужно сортировать, то вы можете просто вывести остаток массива из сводной таблицы. Поскольку быстрая сортировка может быть выполнена на месте, для этого требуется пространство O (n), а поскольку вы делите половину части массива (в среднем), которую вы проверяете каждый раз, это занимает O (2n) == O (n) времени
Ответ 10
Просто отсортируйте массив с помощью Merge Sort, а затем напечатайте первое число k, в худшем случае будет n * log2 (n).
Ответ 11
Как использовать кучу для хранения значений. Эта стоимость равна n, когда вы просматриваете каждое значение в массиве.
Затем перейдите в кучу, чтобы получить наименьшие значения k.
Время выполнения равно O (n) + O (k) = O (n)
Конечно, пространство памяти теперь O (n + n)
Ответ 12
Как уже упоминалось, есть два способа выполнить такую задачу:
1) Вы можете отсортировать весь массив элементов n с помощью quicksort, heapsort или любой алгоритм сортировки O (n log n), который вы хотите, а затем выберите наименьшие значения m в вашем массиве. Этот метод будет работать в O(n log n).
2) Вы можете использовать алгоритм выбора, чтобы fink m наименьшие элементы в вашем массиве. Потребуется O(n) время, чтобы найти k-е наименьшее значение, так как вы будете повторять этот алгоритм m раз, общее время будет m x O(n) = O(n).
Ответ 13
Это небольшое изменение в базовом условии рекурсии в алгоритме выбора для возврата указателя на динамический массив, содержащий все первые k наименьших элементов в случайном порядке, это O (n).
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *A, int left, int right){
int pivot = A[right], i = left, x;
for (x = left; x < right; x++){
if (A[x] < pivot){
swap(&A[i], &A[x]);
i++;
}
}
swap(&A[i], &A[right]);
return i;
}
int* quickselect(int *A, int left, int right, int k){
//p is position of pivot in the partitioned array
int p = partition(A, left, right);
//k equals pivot got lucky
if (p == k-1){
int*temp = malloc((k)*sizeof(int));
for(int i=left;i<=k-1;++i){
temp[i]=A[i];
}
return temp;
}
//k less than pivot
else if (k - 1 < p){
return quickselect(A, left, p - 1, k);
}
//k greater than pivot
else{
return quickselect(A, p + 1, right, k);
}
}
