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
相似问题