LeetCode215

发表于 | 分类于 ，

题目：

　　在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路：

　　1.最直接的思路就是排序后取k-1索引处的值
　　2.利用快排中的partition函数，partition函数可以在O(n)时间复杂度内找出数组中第k大的数字
　　3.利用最小堆。设置最小堆的大小为k，循环将数组中的值加入最小堆，当超如k容量时取出最小值，这样完成循环后堆顶即为第k大的数。

代码：

2.partition函数：

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
30
31
32
33
34
35
36
   public int findKthLargest(int[] nums, int k) {
   	int low = 0;
   	int high = nums.length - 1;
       int index = partition(nums, low, high);
       while(index != nums.length-k) {
       	if (index > nums.length-k) {
			index = partition(nums, low, index-1);
		}else {
			index = partition(nums, index+1, high);
		}
       }
       return nums[index];
   }
    public static int partition(int[] nums,int low,int high) {
	int x = nums[low];
	int i = low;
	int j = high;
	while(i < j) {
		while(nums[j] >= x && i < j) {
			j--;
		}
		if (i < j) {
			nums[i] = nums[j];
			i++;
		}
		while(nums[i] <= x && i < j) {
			i++;
		}
		if (i < j) {
			nums[j] = nums[i];
			j--;
		}
	}
	nums[i] = x;
	return i;
}

2.最小堆

1
2
3
4
5
6
7
8
9
10
 public int findKthLargest1(int[] nums, int k) {
 	PriorityQueue<Integer> heap = new PriorityQueue<>();
 	for(int n:nums) {
 		heap.add(n);
 		if (heap.size() > k) {
	heap.poll();
}
 	}
 	return heap.poll();
 }

复杂度分析及总结：

1.partition函数：

　　时间复杂度：
　　　　O(n)。？？？
　　空间复杂度：
　　　　O(1)。

2.最小堆：

　　时间复杂度：
　　　　O(nlogk)。？？？
　　空间复杂度：
　　　　O(k)。
　　总结：
　　　　注意Java中堆可以用PriorityQueue实现。