LeetCode热题100--215. 数组中的第K个最大元素--中等

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

题解

publicclassSolution{privateintquickSelect(List<Integer>nums,intk){// 随机选择基准数Randomrand=newRandom();intpivot=nums.get(rand.nextInt(nums.size()));// 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中List<Integer>big=newArrayList<>();List<Integer>equal=newArrayList<>();List<Integer>small=newArrayList<>();for(intnum:nums){if(num>pivot)big.add(num);elseif(num<pivot)small.add(num);elseequal.add(num);}// 第 k 大元素在 big 中，递归划分if(k<=big.size())returnquickSelect(big,k);// 第 k 大元素在 small 中，递归划分if(nums.size()-small.size()<k)returnquickSelect(small,k-nums.size()+small.size());// 第 k 大元素在 equal 中，直接返回 pivotreturnpivot;}publicintfindKthLargest(int[]nums,intk){List<Integer>numList=newArrayList<>();for(intnum:nums){numList.add(num);}returnquickSelect(numList,k);}}

解析

出自：215. 数组中的第 K 个最大元素（分治，清晰图解）

List<Integer>less=newArrayList<>();//创建一个新的列表用于存放小于pivot的数。List<Integer>greater=newArrayList<>();//同样，用于存放大于pivot的数。for(intnum:nums){//遍历nums中的每个数字num：if(num<pivot)//如果num小于基准数，将num添加到"less"列表中；less.add(num);elseif(num>pivot)//如果num大于基准数，将num添加到"greater"列表中。greater.add(num);}// 第 k 大的数字位于 "greater" 或与其大小相同的元素中。if(k<=greater.size())//如果k小于等于"greater"的大小，说明我们正在寻找的元素在"greater"列表中。所以需要调用quickSelect函数，参数为(greater, k)。returnquickSelect(greater,k);else//否则，说明我们要找的数字不在列表 "greater" 和 "equal"（这些与基准数相等的元素）中，而在 "less" 列表中。所以将 k 减去 greater.size() 并递归调用 quickSelect(),参数为(less, k-less.size())returnquickSelect(less,k-greater.size());}publicintfindKthLargest(int[]nums,intk){List<Integer>list=newArrayList<>();//初始化一个新的ArrayList作为临时的list，用于存放数字。for(inti=0;i<nums.length;i++)//将原始数组转换为list格式进行处理。list.add(nums[i]);returnquickSelect(list,k);//返回调用quickSelect函数的值（找到第k大的数字）。}