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大:)

0
1
jxd134
估计是p的取值范围问题,我再尝试修改一下。
2017-09-19
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7446 学习 · 1159 问题

查看课程