12ms C++ partition recursive solution. Any Improvement ?


  • 0
    E

    int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    if (n==1) return nums[0];
    int big = nums[0], small = big;
    vector<int> left;
    vector<int> right;
    for (int i = 1; i < n; i++) {
    if (nums[i] > big)
    big = nums[i];
    if (nums[i] < small)
    small = nums[i];
    }
    const double mid = (big + small) / 2.0; // use the medium as partition pivot
    for (int i = 0; i < n; i++) {
    if (nums[i] <= mid)
    left.push_back(nums[i]);
    else
    right.push_back(nums[i]);
    }
    if (left.size() == n) return nums[0]; // all the elements are equal.
    if (left.size() >= n-k+1)
    return findKthLargest(left, k-right.size());
    else
    return findKthLargest(right, k);
    }

    What are the time complexity and space complexity ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.