如何获取数组前N个值的索引?

我有一个包含数字的大尺寸数组,有没有办法找到前n个值的索引? C中的任何lib函数?

例:

数组:{1,2,6,5,3}

前两个数字的指数是:{2,3}

如果在top n表示数组中第n个最高(或最低)的数字,您可能需要查看QuickSelect算法。 不幸的是,没有C库函数我知道实现它,但维基百科应该给你一个很好的起点。

QuickSelect平均为O(n),如果O(nlogn)和一些开销也很好,你可以做qsort并取第n个元素。

编辑 (作为示例)使用这两种方法,在单个批处理中获取top-n的所有索引都很简单。 QuickSelect将它们全部分类到最终枢轴的一侧。

所以你想要N个数字的大数组中的前n个数字。 有一种简单的算法,即O(N * n)。 如果n很小(看起来像你的情况)这就足够了。

 size_t top_elems(int *arr, size_t N, size_t *top, size_t n) { /* insert into top[0],...,top[n-1] the indices of n largest elements of arr[0],...,arr[N-1] */ size_t top_count = 0; size_t i; for (i=0;i= arr[top[1]] >= .... >= arr[top[top_count-1]] // are the indices of the top_count larger values in arr[0],...,arr[i-1] // top_count = max(i,n); size_t k; for (k=top_count;k>0 && arr[i]>arr[top[k-1]];k--); // i should be inserted in position k if (k>=n) continue; // element arr[i] is not in the top n // shift elements from k to top_count size_t j=top_count; if (j>n-1) { // top array is already full j=n-1; } else { // increase top array top_count++; } for (;j>k;j--) { top[j]=top[j-1]; } // insert i top[k] = i; } return top_count; }