【Hot100】LeetCode—215. 数组中的第K个最大元素

---

• 原题毗连：215. 数组中的第K个最大元素
  

---

1- 思绪

快速选择

• 第 k 大的元素的数组下标： int target = nums.length - k
  

1- 根据 partition 分割的区间来判断当前处理处罚方式

• 如果返回的 int 即是 target 分析找到了，直接返回
  
• 如果返回的 int 小于 target 分析要在当前区间的右侧探求，也就是 [pivotIndex+1,right]
  
• 如果返回的 int 大于 target 分析要在当前区间的左侧探求，也就是 [left,pivotIndex-1]
  

2- 实现 partition 随机选取一个 pivotIndex 分割区间

• 2-1 随机选择一个下标
  
• 2-2 互换 left 和 随机下标
  
• 2-3 将随机下标的元素值设置为 pivot
  
• 2-4 界说 le、ge 下标 使用 while(true)
  
  
  
  • 使得 le 指向的元素始终小于 pivot
    
  • 使得 ge 指向的元素始终大于 pivot
    
  
  

---

2- 实现

⭐215. 数组中的第K个最大元素——题解思绪

1. import java.util.Random;
2. class Solution {
5.     static Random random = new Random(System.currentTimeMillis());
6.     public int findKthLargest(int[] nums,int k){
7.         return quickSelect(nums,0,nums.length-1,nums.length-k);
9.     }
11.     public int quickSelect(int[] nums,int left,int right,int kIndex){
12.         if(right==left){
13.             return nums[left];
14.         }
15.         //
16.         int pivotIndex = partition(nums,left,right);
18.         if(pivotIndex == kIndex){
19.             return nums[kIndex];
20.         }else if( pivotIndex>kIndex){
21.             return quickSelect(nums,left,pivotIndex-1,kIndex);
22.         }else{
23.             return quickSelect(nums,pivotIndex+1,right,kIndex);
24.         }
25.     }
27.     public int partition(int[] nums,int left,int right){
28.         int randomIndex = left + random.nextInt(right-left+1);
29.         swap(nums,left,randomIndex);
31.         int mid = nums[left];
32.         int le = left+1;
33.         int ge = right;
34.         while(true){
35.             while(le<=ge && nums[le] < mid){
36.                 le++;
37.             }
38.             while(le<=ge && nums[ge] > mid){
39.                 ge--;
40.             }
41.             if(le>=ge){
42.                 break;
43.             }
44.             swap(nums,le,ge);
45.             le++;
46.             ge--;
47.         }
48.         swap(nums,left,ge);
49.         return ge;
50.     }
52.     public void swap(int[] nums,int left,int right){
53.         int tmp = nums[left];
54.         nums[left] = nums[right];
55.         nums[right] = tmp;
56.     }
59. }

复制代码

---

3- ACM实现

1. public class kthNums {
3.     static Random random = new Random(System.currentTimeMillis());
4.     public static int findK(int[] nums,int k){
5.         // 快速选择 ，传四个参数
6.         return quickSelect(nums,0,nums.length-1,nums.length-k);
8.     }
10.     public static int quickSelect(int[] nums,int left,int right,int kIndex){
11.         if(right==left){
12.             return nums[left];
13.         }
14.         //
15.         int pivotIndex = partition(nums,left,right);
17.         if(pivotIndex == kIndex){
18.             return nums[kIndex];
19.         }else if( pivotIndex>kIndex){
20.             return quickSelect(nums,left,pivotIndex-1,kIndex);
21.         }else{
22.             return quickSelect(nums,pivotIndex+1,right,kIndex);
23.         }
24.     }
26.     public static int partition(int[] nums,int left,int right){
27.         int randomIndex = left + random.nextInt(right-left+1);
28.         swap(nums,left,randomIndex);
30.         int mid = nums[left];
31.         int le = left+1;
32.         int ge = right;
33.         while(true){
34.             while(le<=ge && nums[le] < mid){
35.                 le++;
36.             }
37.             while(le<=ge && nums[ge] > mid){
38.                 ge--;
39.             }
40.             if(le>=ge){
41.                 break;
42.             }
43.             swap(nums,le,ge);
44.             le++;
45.             ge--;
46.         }
47.         swap(nums,left,ge);
48.         return ge;
49.     }
51.     public static void swap(int[] nums,int left,int right){
52.         int tmp = nums[left];
53.         nums[left] = nums[right];
54.         nums[right] = tmp;
55.     }
57.     public static void main(String[] args) {
58.         Scanner sc = new Scanner(System.in);
59.         String input = sc.nextLine();
60.         String[] parts = input.split(" ");
61.         int[] nums = new int[parts.length];
62.         for(int i = 0 ; i < nums.length ; i++){
63.             nums[i] = Integer.parseInt(parts[i]);
64.         }
65.         System.out.println("输入K");
66.         int k = sc.nextInt();
67.         System.out.println("结果是"+findK(nums,k));
69.     }
70. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金