第K大元素

题目描述

在数组中找到第k大的元素。

给出数组 [9,3,2,4,8],第三大的元素是 4

给出数组 [1,2,3,4,5],第一大的元素是 5,第二大的元素是 4,第三大的元素是 3,以此类推

要求时间复杂度为O(n),空间复杂度为O(1)

问题分析

如果不考虑时间复杂度和空间复杂度,这道题目有很多种方法,利用一种排序算法将数组倒叙排序,第k个数就是第k大元素。

题目的重点在于返回第K大元素,而其他元素并不关心。如果要返回第K大元素,必然要先找到比K大的k-1个数,这k-1个数的顺序也并不用关心。如果我们使用冒泡、选择等常规排序,需要从最大的开始找起,那么时间复杂度就是O(n * k),当k较大时,时间复杂度太高。

快速排序算法的特点就在于经过一次遍历,可以分别找到比某个元素小的数和大的数,如果比这个元素大的数的个数恰好是k-1,那么这个数就正是我们要找的数。假如经过一次遍历之后,元素A左边的元素均大于A,右边的元素均小于A,A的数组下标是index,若index+1=k,那么A就是第k大元素;若index+1>k,那么第k大元素就在数组的0~index-1中,此时问题就变为了在数组的0~index-1中寻找第k大元素,继续循环遍历操作直到存在某个index使index+1=k为止;若index+1<k,那么第k大元素就在数组的index+1~length-1中,循环遍历子数组知道找到某个index使index+1=k即可。时间复杂度=O(n + n/2 + n/4 + … + 1)<O(2n)=O(n)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int kthLargestElement(int n, int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int index = low - 1;
for (int i = low; i < high; i++) {
if (nums[i] > nums[high]) {
swap(nums, i, ++index);
}
}

swap(nums, high, ++index);

if (index + 1 == n) {
return nums[index];
} else if (index + 1 > n) {
high = index - 1;
} else {
low = index + 1;
}
}
return -1;
}

private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
-------------本文结束感谢您的阅读-------------