南昌公司做网站,禁止 wordpress ajax,wordpress修改顶部颜色,宜春住房和城乡建设部网站目录 1- 思路快速选择 2- 实现⭐215. 数组中的第K个最大元素——题解思路 3- ACM实现 原题连接#xff1a;215. 数组中的第K个最大元素 1- 思路
快速选择
第 k 大的元素的数组下标#xff1a; int target nums.length - k
1- 根据 partition 分割的区间来判断当前处理方式… 目录 1- 思路快速选择 2- 实现⭐215. 数组中的第K个最大元素——题解思路 3- ACM实现 原题连接215. 数组中的第K个最大元素 1- 思路
快速选择
第 k 大的元素的数组下标 int target nums.length - k
1- 根据 partition 分割的区间来判断当前处理方式
如果返回的 int 等于 target 说明找到了直接返回如果返回的 int 小于 target 说明要在当前区间的右侧寻找也就是 [pivotIndex1,right]如果返回的 int 大于 target 说明要在当前区间的左侧寻找也就是 [left,pivotIndex-1]
2- 实现 partition 随机选取一个 pivotIndex 分割区间
2-1 随机选择一个下标2-2 交换 left 和 随机下标2-3 将随机下标的元素值设置为 pivot2-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(rightleft){return nums[left];}//int pivotIndex partition(nums,left,right);if(pivotIndex kIndex){return nums[kIndex];}else if( pivotIndexkIndex){return quickSelect(nums,left,pivotIndex-1,kIndex);}else{return quickSelect(nums,pivotIndex1,right,kIndex);}}public int partition(int[] nums,int left,int right){int randomIndex left random.nextInt(right-left1);swap(nums,left,randomIndex);int mid nums[left];int le left1;int ge right;while(true){while(lege nums[le] mid){le;}while(lege nums[ge] mid){ge--;}if(lege){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(rightleft){return nums[left];}//int pivotIndex partition(nums,left,right);if(pivotIndex kIndex){return nums[kIndex];}else if( pivotIndexkIndex){return quickSelect(nums,left,pivotIndex-1,kIndex);}else{return quickSelect(nums,pivotIndex1,right,kIndex);}}public static int partition(int[] nums,int left,int right){int randomIndex left random.nextInt(right-left1);swap(nums,left,randomIndex);int mid nums[left];int le left1;int ge right;while(true){while(lege nums[le] mid){le;}while(lege nums[ge] mid){ge--;}if(lege){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));}
}
