找第K大元素问题
来源：7-1 二叉树天然的递归结构
慕村1059658
2019-03-08
老师，请问这里为什么要判断：
if(lo==hi) return nums[lo];
我注释掉也可以正常运行
public int findKthLargest(int[] nums, int lo, int hi, int k) {
if(lo==hi)
return nums[lo];//???????
int j = partition(nums, lo, hi);
if(j==k)
return nums[k];
else if(j<k)
return findKthLargest(nums,j+1,hi,k);
else
return findKthLargest(nums,lo,j-1,k);
}
写回答
1回答
-
liuyubobobo
2019-03-08
整个函数的语义是：
在nums[lo...hi]区间中，寻找第k大的数。
那么，在lo==hi的时候，也就是当前所寻找的区间中只有一个元素的时候，这个元素本身肯定就是我们要寻找的数。这是递归结束的一个平凡解。
扔掉这个判断，确实可以执行，因为如果lo==hi的时候，partition的结果j肯定是这个lo(也是这个hi，也是这个k)，所以返回nums[k]，得到了正确的结果。这两个条件虽然看起来很不相同，但往下深挖，底层逻辑是重叠的：）
不过，我们在写函数的时候，可能会很难想清楚，这两个看似如此不同的条件是重叠的。我们在写一个递归函数，在这里，我是按照标准的写清楚递归到底情况和递归过程两段式的方式进行的书写：）
public int findKthLargest(int[] nums, int lo, int hi, int k) { // 递归到底的情况，当前寻找的区间只有一个元素 if(lo==hi) return nums[lo]; // 递归过程，处理nums[lo...hi]区间 int j = partition(nums, lo, hi); if(j==k) return nums[k]; else if(j<k) return findKthLargest(nums,j+1,hi,k); else return findKthLargest(nums,lo,j-1,k); }当然，如果你在写这个逻辑的时候，可以清晰地意识到，这个递归到底的情况和下面的逻辑有重合，大赞！当然没问题啦：）
继续加油！：）
00
相似问题