image.png

注意 quikselect 模板

算法导论
这是以right作为pivoit的情况；

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    int partition(vector<int> &a, int left, int right){
        int pivoit  = a[right];
        int i = left - 1;
        for(int j= left; j <= right-1; j++){
            if(a[j] <= pivoit){
                i++;
                swap(a[i], a[j]);
            }
        }
        swap(a[i+1], a[right]);
        return i+1;
    }
    int median(vector<int> &nums) {
        // write your code here
        int left = 0;
        int right = nums.size() - 1;
        int median = (nums.size()-1)>>1;
        //cout<<nums[0]<<endl;
        while(left <= right){
            //cout<<nums[median]<<endl;
            int index = partition(nums,left, right);
            cout<<index<<endl;
            if(index == median){
                //cout<<nums[median]<<endl;
                return nums[median];
            }
            if(index < median){
                left = index + 1;
            }
            else{
                right = index - 1;
            }
        }
        
    }
};

以left为pivoit的情况：

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    int partition(vector<int> &a, int left, int right){
        int pivoit  = a[left];
        int i = left;
        for(int j= left+1; j <= right; j++){
            if(a[j] <= pivoit){
                i++;
                swap(a[i], a[j]);
            }
        }
        swap(a[i], a[left]);
        return i;
    }
    int median(vector<int> &nums) {
        // write your code here
        int left = 0;
        int right = nums.size() - 1;
        int median = (nums.size()-1)>>1;
        //cout<<nums[0]<<endl;
        while(left <= right){
            //cout<<nums[median]<<endl;
            int index = partition(nums,left, right);
            cout<<index<<endl;
            if(index == median){
                //cout<<nums[median]<<endl;
                return nums[median];
            }
            if(index < median){
                left = index + 1;
            }
            else{
                right = index - 1;
            }
        }
        
    }
};