【Hot100】LeetCode—215. 数组中的第K个最大元素
目录
- 1- 思路
- 快速选择
- 2- 实现
- ⭐215. 数组中的第K个最大元素——题解思路
- 3- ACM实现
- 原题连接: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个最大元素——题解思路
import java.util.Random;
class Solution {static Random random = new Random(System.currentTimeMillis());public int findKthLargest(int[] nums,int k){return quickSelect(nums,0,nums.length-1,nums.length-k);}public int quickSelect(int[] nums,int left,int right,int kIndex){if(right==left){return nums[left];}//int pivotIndex = partition(nums,left,right);if(pivotIndex == kIndex){return nums[kIndex];}else if( pivotIndex>kIndex){return quickSelect(nums,left,pivotIndex-1,kIndex);}else{return quickSelect(nums,pivotIndex+1,right,kIndex);}}public int partition(int[] nums,int left,int right){int randomIndex = left + random.nextInt(right-left+1);swap(nums,left,randomIndex);int mid = nums[left];int le = left+1;int ge = right;while(true){while(le<=ge && nums[le] < mid){le++;}while(le<=ge && nums[ge] > mid){ge--;}if(le>=ge){break;}swap(nums,le,ge);le++;ge--;}swap(nums,left,ge);return ge;}public void swap(int[] nums,int left,int right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;}}
3- ACM实现
public class kthNums {static Random random = new Random(System.currentTimeMillis());public static int findK(int[] nums,int k){// 快速选择 ,传四个参数return quickSelect(nums,0,nums.length-1,nums.length-k);}public static int quickSelect(int[] nums,int left,int right,int kIndex){if(right==left){return nums[left];}//int pivotIndex = partition(nums,left,right);if(pivotIndex == kIndex){return nums[kIndex];}else if( pivotIndex>kIndex){return quickSelect(nums,left,pivotIndex-1,kIndex);}else{return quickSelect(nums,pivotIndex+1,right,kIndex);}}public static int partition(int[] nums,int left,int right){int randomIndex = left + random.nextInt(right-left+1);swap(nums,left,randomIndex);int mid = nums[left];int le = left+1;int ge = right;while(true){while(le<=ge && nums[le] < mid){le++;}while(le<=ge && nums[ge] > mid){ge--;}if(le>=ge){break;}swap(nums,le,ge);le++;ge--;}swap(nums,left,ge);return ge;}public static void swap(int[] nums,int left,int right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();String[] parts = input.split(" ");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length ; i++){nums[i] = Integer.parseInt(parts[i]);}System.out.println("输入K");int k = sc.nextInt();System.out.println("结果是"+findK(nums,k));}
}