215. Kth Largest Element in an Array
来源:3-5 三路快排partition思路的应用 Sort Color
jxd134
2017-09-18
class Solution {
private:
int partition(vector<int>& nums, int l, int r)
{
int p = rand() % (r - l + 1) + l;
swap(nums[l], nums[p]);
int j = l;
for(int i = l + 1; i<= r; ++i)
if(nums[i] < nums[l])
swap(nums[i], nums[++j]);
swap(nums[l], nums[j]);
return j;
}
int selection(vector<int>&nums, int l, int r,int k)
{
if(l == r)
return nums[l];
int p = partition(nums, l ,r);
if(k == p)
return nums[p];
else if(k < p)
return selection(nums, l, p-1, k);
else
return selection(nums, p + 1, r, k);
}
public:
int findKthLargest(vector<int>& nums, int k) {
if(nums.size() <= 0)
return 0;
return selection(nums, 0 , nums.size() - 1, k);
}
};Leetoce上一直无法通过测试,提示Runtime Error Message:Line 5: division by zero。
无法获取测试集反推原因,求问是什么原因?
写回答
1回答
-
liuyubobobo
2017-09-18
应该是 int p = rand() % (r - l + 1) + l; 这句话里 r-l+1 有可能为0,换句话说你在调用selection的时候,传入的l和r值有可能l比r大:)
012017-09-19
相似问题