A simple CPP solution with std::partition


  • 3
    K

    Here I use std::partition rather than implement it myself.

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            auto first = nums.begin(), last = nums.end();
            auto target = first + k - 1;
            while (first < last) {
                auto mid = partition(first, last - 1, [last] (int e) { return e > *(last - 1); } );
                swap(*mid, *(last - 1));
                if (mid < target) {
                    first = mid + 1;
                } else if (mid > target) {
                    last = mid;
                } else {
                    break;
                }
            }
            return *target;
        }
    };
    

    As requested by @samoshka, here I make a simple explanation about the lambda expression above.

    The syntax [last] (int e) { return e > *(last - 1); } is equal to anonymously define a function like:

    bool anonymous(int e) {
        return e > *(last - 1);
    }
    

    And the variable last is captured/copied from the outer scope by value,


  • 1
    S

    Can you please explain/give link to the explanation of the syntax: [last] (int e) { return e > *(last - 1);}

    I haven't come across lambda in CPP yet..


  • 0

    Is *(last - 1) evaluated before partition runs? Or every time the lambda is used? If the latter, doesn't partition change the value of *(last - 1) during it's run and thus potentially change the lambda during the run?


  • 0
    K

    Yes, it's the later one. But what you worry about will not happen, because partition works on the range [first, last - 1).


  • 0

    Ah, right, I missed the "- 1" in the second parameter. Thanks.


  • 0
    H

    I found this video that explains lambda pretty well.
    https://www.youtube.com/watch?v=5t-_wI7nFdU


Log in to reply
 

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