本文主要是介绍leetcode:Kth Largest Element in an Array 使用快速选择算法，以及对其复杂度的分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
题目分析：找到第K个大的数，首先想到就是排好序后，找到nums[len-k]就是结果，这样复杂度为o(nlogn),又想我们不需要把每个数都排好，只要求K前面的比K小，K后面的比K大，那么我们可以考虑选择排序，并且为了快速找到，我们可以采用二分法，根据随机值将nums一分为二，并且选定某一部分查找，丢弃剩余的另一部分，复杂度为O(n+1/2*n+1/4*n+....)=O(2n)
具体代码如下：
public int findKthLargest(int[] nums, int k) {//返回的是排好序后的nums[length-k]return findK(nums,nums.length-k,0,nums.length-1);}/*** * @param nums* @param k 排序后的下标* @param i* @param j* @return*/public int findK(int[] nums,int k,int i,int j){ if(i>=j) return nums[i];int m=partition(nums,i,j);if(m==k) return nums[m];else if(k<m) return findK(nums,k,i,m-1);else return findK(nums,k,m+1,j);}//将nums在i到j范围内分为左右两个部分，左边的小于nums[i],右边的大于等于nums[i],返回的是选择排序后m下标/*** * @param nums 数组* @param i 被分割的起始位置* @param j 被分割的结束位置* @return*/public int partition(int[] nums,int i,int j){int x=nums[i];int m=i;int n=i+1;//遍历，遇到比X小的交换，并且m后移while(n<=j){if(nums[n]<x){swap(nums,++m,n);}n++; }swap(nums,i,m);return m;}public void swap(int[] nums,int i,int j){int tmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}这篇关于leetcode:Kth Largest Element in an Array 使用快速选择算法，以及对其复杂度的分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
