LeetCode 腾讯精选50题--数组中的第K个最大元素
好吧,不得不承认,书上看到的始终不是自己的,只有亲身时间过才会明白该怎么操作。
找数组中第K个最大元素,简而言之就是先排序,不论使用哪种算法,都需要先排序,确认位置,由于数组可以通过下标直接访问,所以我打算将数组按逆序排序,选择算法方面,一开始打算使用大顶堆的堆排序,可是想了下,快排的性能会更好一点,所以就采用快排了
具体思路如下:
由于一开始为了让空间复杂度为O(1),所以踩了不少坑,最坑的就是找到中间位置,又要让比中间元素小的放在左边,又不打算移动中间位置,直接就崩了。。。惨惨惨。
言归正传:
1. 首先明确一点就是快排使用递归操作
2. 其次利用三元法确定pivot,即元素的界,值小于pivot放在右侧,大于pivot的但在左侧
3. 根据k的大小确定递归哪一侧
具体程序如下:
1 package algorithm;
2
3 public class QuickSort {
4
5 public int findKthLargest(int[] nums, int k){
6 if(nums.length < k){
7 return 0;
8 }
9 quickSort(nums,0,nums.length-1,k);
10
11 return nums[k-1];
12 }
13
14 private void quickSort(int[] nums,int left,int right,int k){
15
16 int center = (left+right)/2;
17 if(left >= right){
18 return;
19 }
20 int pivot = chosePivot(nums,left,right,center);
21
22 int i = left+1;
23 int j= right-1;
24 while (i < j){
25 while (nums[i++] >= nums[center] && i < center){
26 i++;
27 }
28 while (nums[j--] < nums[center] && j > center){
29 j--;
30 }
31
32 if(nums[i] <= pivot && pivot <= nums[j]){
33 swap(nums,i,j);
34 if(i == center){
35 center = j;
36 }else if(j == center){
37 center = i;
38 }
39 }
40 }
41 if(k <= center){
42 quickSort(nums,left,center,k);
43 }else if(k > center){
44 quickSort(nums,center+1,right,k);
45 }
46
47
48 }
49
50 private int chosePivot(int[] nums,int left,int right,int center){
51 if(nums[right] > nums[center]){
52 swap(nums,right,center);
53
54 }
55 if(nums[left] < nums[right]){
56 swap(nums,left,right);
57
58 }
59
60 if(nums[left] < nums[center]){
61 swap(nums,left,center);
62 }
63
64
65 return nums[center];
66
67 }
68
69 private void swap(int[] nums,int left,int right){
70 int temp = nums[left];
71 nums[left] = nums[right];
72 nums[right] = temp;
73 }
74
75 public static void main(String[] args){
76 int[] nums = new int[]{3,2,1,5,6,4};
77
78 QuickSort sort = new QuickSort();
79
80
81 System.out.println(sort.findKthLargest(nums,2));
82 for (int i: nums){
83 System.out.print(i);
84 }
85 }
86
87
88 }
后续会在继续考虑优化问题,展示先这样了
转载于//www.cnblogs.com/Kaithy-Rookie/p/11305385.html
还没有评论,来说两句吧...