java求数组中第K大的数

这是我在面试中面试官问过我的一个问题，网上也有很多人说遇到过这样的问题，说实话这个题很操蛋也很经典，选对方法才是关键。

public static void main(String[] args)

{
      //求数组中第K大的数
      int [] n={1,23,12,12,12,58,24,44,32,56,56,56,67,23,44};
      repeat(n,5);
 
       //求集合中第K大的数
       List list = new ArrayList();
       list.add(0, 1);
       list.add(1, 23);
       list.add(2,12);
       list.add(3,58);
       list.add(4,24);                                                     
       list.add(5,44);
 
       int [] array = new int[list.size()];
       for(int i=0;i<list.size();i++)
       {
        array[i]=(Integer) list.get(i);
       }
       repeat(array,5);
}

//获取数组中第K大的数方法
private static void repeat(int [] a,int k)

{
       Arrays.sort(a);
       int count=0;
       for(int x =a.length-1;x>=0;x--)
       {
             if(a[x-1]!=a[x])
             {
                   count++;
                   if(count==k)
                   {
                         System.out.println("第"+k+"大的数是："+a[x]);
                         break;
                   }
              }
       }
}

有兴趣的可以加群：203609918，我们一起进步！！！

评论

6 楼 albrich 2012-03-07  

837062099 写道

算法复杂度太高了，应该用二分法。

二分法好像不能过滤掉重复的数据，比如int[] num={1,2,2,3},如果求第三大的数，它就会输出2，而不是3

5 楼 xlaohe1 2012-03-02  

public static void gMax(int index) {
		int [] n={1,23,12,12,12,58,24,44,32,56,56,56,67,23,44};
		Set<Integer> set = new TreeSet<Integer>(); // treeSet auto sort
		for(int i = 0; i < n.length; i ++) 
			set.add(n[i]);
		for(int i : set)
			System.out.print(i + " ");
		System.out.println();
		if(index == 0){ // not enter 0
			System.out.println("Enter error");
			return;
		}
		if(index - 1 < set.size()) // index begin 1
			System.out.println(set.toArray()[set.size() - index]);
		else
			System.out.println("Not found");
	}

4 楼 xfjt297857539 2012-03-02  

837062099 写道

算法复杂度太高了，应该用二分法。

二分法?大概代码能写一下吗？

3 楼 837062099 2012-03-02  

yuelangyc 写道

先把数组排序然后取第K个数可以么。

可以啊，不过算法不太好，先排序几乎是万能的方法。

2 楼 yuelangyc 2012-03-02  

先把数组排序然后取第K个数可以么。

1 楼 837062099 2012-03-02  

算法复杂度太高了，应该用二分法。