在n个项目的数组中findk个最小数字的algorithm
我试图编写一个algorithm，它可以在O（n）时间内打印n个大小数组中的k个最小数字，但是我不能将时间复杂度降低到n。 我该怎么做？
我之前在一次采访中已经这样做了，最优雅/有效的方法之一就是这样
O(n log k). with space: O(k) (thanks, @Nzbuu) 基本上你会使用一个大小限于k的最大堆。 对于数组中的每个项目，检查它是否小于最大值（仅O（1））。 如果是这样，把它放在堆（O（log k））中，并删除最大值。 如果它更大，去下一个项目。
当然，堆不会产生k个项目的sorting列表，但可以在O（k log k）中完成，这很容易。
同样的，你也可以用同样的方法find最大的k个项目，在这种情况下你可以使用min-heap。
您将需要使用“selectalgorithm”（即O（n））find第k个最小的元素，然后再次迭代该数组并返回每个小于/等于它的元素。
selectalgorithm： http : //en.wikipedia.org/wiki/Selection_algorithm
你必须注意，如果你有重复：你将需要确保你没有返回更多的K元素（这是可能的，例如，如果你有1,2，…，K，K，K .. 。）
编辑：
完整的algorithm，并根据要求返回一个列表：让数组成为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
请注意，如果您的列表可能有重复，则需要第三次迭代。 如果不行 – 这是不必要的，只要把4.1中的条件改为<=。
还要注意：L.add将一个元素插入到链表中，因此是O（1）。
假设您试图显示K个最小的数字，您可以使用Hoare's Selectalgorithm来查找第k 个最小的数字。 将数组分成较小的数字，第k 个数字和较大的数字。
这可以在预期的线性时间（O（n））中完成。 首先find数组的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]); } }
这个问题的最佳解决scheme如下。使用快速sortingfind枢轴，并放弃第k个元素不在的部分，recursion地find下一个枢轴。 （这是第k个最大查找器，您需要更改if else条件以使其成为第k个最小查找器）。这里是JavaScript代码 –
// 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 (ie 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));
只需要用Merge Sort对数组进行sorting，然后打印第一个k数字，在最坏的情况下，它将使用n * log2（n）。
如何使用堆来存储值。 这个成本是n，当你通过数组中的每个值。
然后通过堆得到最小的k值。
运行时间是O（n）+ O（k）= O（n）
当然，内存空间现在是O（n + n）
如前所述，有两种方法可以完成这样的任务：
1）您可以使用快排 ， 堆 sorting或任何O (n log n)sortingalgorithm对整个n元素进行sorting ，然后选取数组中最小的m值。 这个方法将在O(n log n) 。
2）你可以使用selectalgorithm来链接数组中的最小元素。 要花费O(n)时间才能find第k个最小值，因为你将迭代这个algorithmm次，总时间将是mx O(n) = O(n) 。
有可能在O(n)时间中findn个元素中的最小的k个元素O(n)我的意思是真正的O(n)时间，而不是O(n + some function of k) ）。 请参阅维基百科文章“selectalgorithm” ，特别是“无序部分sorting”和“中位数select作为枢轴策略”的小节，以及关于制作O(n)的基本作品的文章“中位数” 。
我不知道你在找什么，但很简单的O（n * k）时间和O（k）空间。 这是最大的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; }
另一种技术 – 使用QuickSelectalgorithm，结果将是返回结果左侧的所有元素。 平均时间复杂度是O（n），最坏的情况是O（n ^ 2）。 空间复杂性将是O（1）。
