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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
题目
找数组里第K大的元素,这里指的是排好序后,从后往前数第k个数,是包含重复元素的。
思路
快排改造:
如果是有序数组,我们一下就能找到第k大的元素,但是所给数组无序,我们就需要先排序,但是又没必要全部排好序,所以可以依照快排思想,稍作改造,顺便复习一下快排。
快排思想:
- 我们在数组里选择一个参考元素,这个参考元素一般选第一个元素,或者随机选一个把它和第一个元素换一下位置。
- 两个指针分别从头尾遍历数组,如果头指针所指元素小于参考元素就继续往后走,尾指针所指元素大于参考元素就继续往前走,若不满足,则停下来,把两个指针元素交换位置,然后继续遍历,直到两指针相遇。
- 遍历一次下来,数组左边的元素都小于等于参考元素,右边的元素都大于等于参考元素,此时再把参考元素(第一个)和两指针相遇位置的元素互换。就完成了第一次快排。
此时数组为:[小于等于参考元素,...,参考元素,...,大于等于参考元素]。 - 分别再对前半段数组和后半段数组重复上述123步骤,最后整个数组就排好了。
针对本题目,我们排完一次,可以判断一下指针的位置:
- 即数组右半边若刚好有k-1个元素,那么中间这个元素就是第k大的元素;
- 若数组右半边的元素数量<k-1个元素,说明第k大的元素在数组左半边;
- 若数组右半边的元素数量>k-1个元素,说明第k大的元素在数组右半边;
- 最后,依据上述不同情况,在特定区间递归寻找即可;
代码实现如下:
代码
public int findKthLargest(int[] nums, int k) {
int l=0;
int r=nums.length-1;
return partition(l,r,nums,k);
}
private int partition(int start, int end, int[] nums,int k) {//快排分区
// int random =(int)(Math.random()*(r-l+1)+l);
// swap(nums,l,random);//先让第一个元素随机交换位置
int i=start;
int j=end;
int v=nums[i];//这里我们就按照第一个元素划分
while (i<j) {
while (i<j&&nums[j]>=v) {//先让j往前走,遇到小于v的停下来。这里一定要先让j走!!
//因为i是从第一个元素开始的,而第一个元素的值已经存在v里了。所以先让j走,去覆盖i,没事。
j--;
}
if(i<j)
nums[i++]=nums[j];//与i交换,同时i往前走
while (i<j&&nums[i]<=v) {//此时i再往后走,遇到大于v的就和j交换,此时j是指向从后往前第一个小于v的数,而且是已经复制过去了,所以这个值是重复的。
i++;
}
if(i<j)
nums[j--]=nums[i];
//找到后交换位置
}
nums[i]=v;//最后一步,把参考元素和指针交换,一轮就分完了
if (k==end-j+1) {//从队尾到v一共k-1个元素的话,那么v就是第k大的元素
return v;
}else if (k<end-j+1) {//比v大的数已经超过k个了,所以第k大的数肯定在这里面
return partition(j+1, end, nums, k);
}else {//否则证明右边还没拍到第k大,所以在坐便继续找,这时注意我们在左边就是找(k-右边这么多元素)就够了
return partition(start, j-1, nums, k-(end-j+1));
}
}
网友评论