求一个数组中最大的前n个数

Question

假设有一个数组，现求出数组中最大的前n个数的下标。输入：一个数组 Input[]
输出：一个数组 Output[]注意：
n是一个未知数。
Input中的数，很具有区分度，大小差别挺大。
Input中的数，有重复的。例：
int Input[] ={1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 200, 12, 180, 190, 220, 221, 3, 5, 226};
//            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,  14,  15,  16,  17,18,19//这里是对应的坐标　public static int[] Compute(int Input[]){        
}输出
Ouput={11,13,14,15,16,19}Output是较大的几个数对应的下标.
可能这是一个算法题。

Answer 1

http://yilee.info/find-the-largest-k-figures-in-the-beauty-of-programming.html

Answer 2

public class SelectSort {
 // 简单选择排序
static void selectSort(int[] array, int[] subscript, int n) {
int i, j, max, tmp;
for (i = 0; i < n; i++) {
max = i;
for (j = i; j < array.length - 1; j++) {
if (array[max] < array[j + 1])
max = j + 1;
}
if (max != i) {
tmp = array[i];
array[i] = array[max];
array[max] = tmp;

tmp = subscript[i];
subscript[i] = subscript[max];
subscript[max] = tmp;
}
}
} public static void main(String[] args) {
int[] input = { 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 200, 12, 180, 190,
220, 221, 3, 5, 226 };
int[] subscript = new int[input.length];
for(int i = 0; i < subscript.length; ++i)
subscript[i] = i;
int n = 6;
selectSort(input, subscript, n);
for(int i = 0; i < n; ++i)
System.out.print(subscript[i] + "  ");
System.out.println();
}}

Answer 3

很简单的 先用sort排序 然后逆序输出前n个数

Answer 4

不知道楼主要的是效率还是仅仅是结果，再说了就算是要的效率的话，我们写的排序算法能有java List类的sort()效率高吗？

Answer 5

建个n大的最小堆就行了
数组规模M，取前n大的数的时间复杂度为O(M*lg(n))