4ms C++ solution with explains


  • 2
    E

    Inspired by QuickSort.

    For an array S, quicksort devide the array into 3 parts everytime. [Sa, D, Sb], Sa is array of items which is greater than D, and Sb is array of items which is less than D.

    • If Sa has K-1 items, the D will be the answer.
    • If Sa has less than K-1 items, the D would be greater than Kth largest number, then we can divide Sb.
    • If Sa has more than K-1 items, the D would be less than Kth largest number, then we can divide Sa.

    Here is code:

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int start = 0;
            int end = nums.size();
            int k1 = k - 1;
            int j, d;
    
            do {
                j = start;
                d = nums[start];
                for (int i = start + 1; i < end; i++) {
                    if (nums[i] > d) {
                        nums[j] = nums[i];
                        nums[i] = nums[j+1];
                        j++;
                    }
                }
                nums[j] = d;
    
                if (j < k1) {
                    start = j+1;
                } else if (j > k1) {
                    end = j;
                }
            } while (j != k1);
    
            return nums[k1];
        }
    };

  • 0
    D

    Great solution.
    I have a question. the parameter "nums" is declaimed to be type reference ("vector<int>&"), while the solution has changed its element values by assignments (eg. nums[j] = nums[i];), which would affect the vector after return. Is that acceptable?


  • 0
    E

    Yes, the original array will be modified. I saw in most puzzles, if the input cannot be changed, there will be an announcement. I haven't seen the announcement in this question. So I made an assumption: the input can be changed.


Log in to reply
 

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