quick select and median-finding, deterministic O(n) time


  • 0
    G

    For explanations, see https://en.wikipedia.org/wiki/Median_of_medians
    Just for fun.

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int n = nums.size(), low = 0, high = n - 1;
            if(n == 0) return -1; //empty case
            while(low < high){
                int mid = partition(nums, low, high);
                if(mid < k - 1)
                    low = mid + 1;
                else if(mid > k - 1)
                    high = mid - 1;
                else return nums[mid];
            }
            return nums[high];
        }
        int partition(vector<int>& nums, int l, int r){
            if(r <= l) return l;
            int pvt = pivot(nums, l, r);
            for(int j = l; j <= r; j++)
                if(nums[j] == pvt){
                    std::swap(nums[j], nums[l]);
                    break;
                }
            int i = l + 1;
            for(int j = i; j <= r; j++)
                if(nums[j] > pvt)
                    std::swap(nums[j], nums[i++]);
            std::swap(nums[l], nums[i - 1]);
            return i - 1;
        }
        int pivot(vector<int>& nums, int l, int r){
            if(r - l < 5)
                return nums[median5(nums, l, r)];
            vector<int> temp;
            for(int i = l; i <= r; ){
                int right = min(r, i + 4);
                int med = median5(nums, i, right);
                temp.push_back(nums[med]);
                i = right + 1;
            }
            return findKthLargest(temp, ( (int)temp.size() + 1) / 2);
        }
        int median5(vector<int>&nums, int l, int r){
            vector<int> temp;
            for(int i = l; i <= r; i++){
                int j;
                for(j = 0; j < temp.size(); j++){
                    if(temp[j] >= nums[i]) break;
                }
                temp.insert(temp.begin() + j, nums[i]);
            }
            for(int i = l; i <= r; i++)
                if(nums[i] == temp[(l+r)/2]) return i;
            return l;
        }
    };
    

Log in to reply
 

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