C++ 12ms partition recursive solution


  • 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 ?


  • 1
    B

    That should depend on the distribution of the elements in the array.


  • 0

    @EvanPerlinHu Quite impressive recursion here. Since

    • you have selected the proper middle number to split the array making the partition comparably even, so each searching array after each round will be always half of the previous round
    • as an apparent result, the space cost will at most 2n (n here is the size of the original array): the first round you will take up n but the second round would only take n/2 since the other half is ignored by the if (left.size() >= n-k+1) and then n/4, n/8...so sum them all up you will get 2*n easily.
    • the time complexity analysis will be quite similar here, O(n) is the final result

  • 0
    E

    @LHearen you are right, thanks for your comment.


  • 0

    @LHearen I think we can't guarantee to separate the array evenly each time. Suppose the array is [17,1,10,14,16] and k = 2. The biggest is 17 and the smallest is 1. We separate into two groups which are left = [1] and right = [10, 14, 16, 17], since the left size is 1 which is smaller than n - k + 1 = 4, we recall findkthLargest with right = [10, 14,16, 17] and k = 2. In the second round, the medium is 13.5, and again, we get left = [10], right = [14,16,17]. Since left size is smaller than 3 (4 - 2 + 1), we call findKthLargest with right = [14,16,17] and k = 2. Then, we get left = [14], right = [16,17] in the next round. You may notice that, since we only remove one element in each round, so we need n, n-1, n-2, ..., 2 operations in each call, which sum up to O(n^2). I am not sure if there is anything wrong with my analysis, so correct me if i am wrong.


  • 0

    @LinHungShi Your analysis is right in the worst case, but usually the partition is proper enough to split the array into even half. I've not posted my optimised version here. Actually to avoid the worst case we can shuffle this whole array before the partition which will effectively be able to avoid the case you mentioned.

    for(int i  = 0; i < size; ++i)
        swap(nums[i], nums[rand()%size]);
    

  • 0

    @LHearen Since the function only separates elements into groups, does shuffling really help?


  • 0

    @LinHungShi It does. But you'd better do more coding and testing before always questioning here.


Log in to reply
 

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