算法题 求第K大的数

题目描述：在乱序数组中求第K大的数

思路：立刻想到的是当然先排序然后取数。但是提问者明显不是想这么解。上网查了下原来是快排思路。

利用快排的思想，从数组arr中随机找出一个元素X，把数组分成两部分arr_a和arr_b。

arr_a中的元素比x大，arr_b中的元素比x小。

这个时候分为两种情况：

1.arr_a中的元素个数小于K，则第K大数在arr_b中

2.arr_a中的元素大于等于K，则返回arr_a中第K大数（只需比较K和X即可）

平均时间复杂度：O（?）（不会算..，望指点）

代码：

public class Test {

	public static void main(String[] args){
		int[] arr={3,1,2,5,4,7,6};  
        int k = 6;
        findK(arr,k,0,arr.length-1);  
	}
	
	public static void findK(int[] a,int k,int left,int right){
		int temp = partition(a,left,right);		//temp是下标，对应第temp-1大的数
		if(temp == k-1){
			System.out.println(a[temp]);
			return ;
		}
		else if(temp > k-1)    //第K大出现在前半段
			findK(a,k,left,temp-1);
		else if(temp < k-1)    //出现在后半段
			findK(a,k,temp+1,right);    
	}
	
	public static int partition(int[] a,int left,int right){
		int pivot = a[left];
		int low = left;
		int high = right;
		while(low < high){
			while(low < high && a[high]<pivot)
				high--;
			swap(a,low,high);
			while(low < high && a[low]>pivot)
				low++;
			swap(a,high,low);
		}
		a[low] = pivot;
		return low;
	}
	public static void swap(int[] t,int a,int b){
		int temp = t[a];
		t[a] = t[b];
		t[b] = temp;
	}
}

借鉴的是这个老哥，但是他的有点瑕疵：https://blog.csdn.net/hqtc0704/article/details/74390512

最后

以上就是强健奇异果为你收集整理的算法题 求第K大的数的全部内容，希望文章能够帮你解决算法题 求第K大的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。