Как получить индексы верхних значений N массива?

У меня есть массив большого размера, который содержит числа, есть ли способ найти индексы верхних n значений? Любая функция lib в C?

пример:

массив: {1,2,6,5,3}

индексы верхнего 2-го числа: {2,3}

Если по top n вы имеете в виду n наивысшее (или самое низкое) число в массиве, вы можете посмотреть на алгоритм QuickSelect . К сожалению, нет функции библиотеки C, которую я знаю о ее реализации, но Википедия должна дать вам хорошую отправную точку.

QuickSelect – это O (n) в среднем, если O (nlogn) и некоторые накладные расходы тоже прекрасны, вы можете выполнить qsort и взять n -й элемент.

Изменить (в ответ на пример) Получение всех индексов топ-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; }