2020-07-21 旋转矩阵&&第k大

1. 旋转矩阵

边界条件比较难控制；还有一种做法是，先上下翻转，再沿对角线翻转。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N = matrix.size();
        if(N == 0)
            return;
        for(int i = 0; i < N / 2; i++){
            int last = N - i - 1;
            for(int j = i; j < last; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[N - j - 1][i];
                matrix[N - j- 1][i] = matrix[N - i - 1][N - j - 1];
                matrix[N - i - 1][N - j - 1] = matrix[j][N - i - 1];
                matrix[j][N - i - 1] = tmp;
            }
        }
    }
};

18 四数之和

跟三数之和一样的思路，设置pq分别为第一和第二个数，然后两个指针ij分别为q+1和N-1；外层循环为p，内层循环为q，双指针。需要注意重复的情况。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        if(nums.size() < 4)
            return ret;
        sort(nums.begin(), nums.end());
        int p = 0;
        for(int p = 0; p < nums.size() - 3; p++){
            if(p >  0 && nums[p] == nums[p - 1])
                continue;
            for(int q = p + 1; q < nums.size() - 2; q++){
                if(q > p + 1 && nums[q] == nums[q - 1])
                    continue;
                int cur_sum = nums[p] + nums[q];
                int i = q + 1, j = nums.size() - 1;
                while(i < j){
                    int tmp = cur_sum + nums[i] + nums[j];
                    if(tmp == target){
                        vector<int> v = {nums[p], nums[q], nums[i], nums[j]};
                        ret.push_back(v);
                        i++;
                        j--;
                        while(i < j && nums[i] == nums[i - 1])
                            i++;
                        while(i < j && nums[j] == nums[j + 1])
                            j--;
                    }
                    else if(tmp < target){
                        i++;
                        while(i < j && nums[i] == nums[i - 1])
                            i++;
                    }
                    else{
                        j--;
                        while(i < j && nums[j] == nums[j + 1])
                            j--;
                    }
                }
            }
        }
        return ret;
    }
};

215 找到第k大的数

用快排的思想，每次选择区间内第一个元素作为pivot，将数组区间分为两部分。如果返回index<k，就搜索右边，否则，搜索左边。
写快排需要注意：mid和k的初始值，以及更新条件。mid初始值是left，k的初始值是left + 1；如果下一个扩展的元素比pivot大，就将左边的区间向右扩展，也就是交换mid和k的值；否则，只更新k。
搜索需要注意：单边搜索，O(logn)。

class Solution {
public:
    void swap(vector<int>& nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    int partition(vector<int>& nums, int left, int right){
        int pivot = nums[left];
        int mid = left;
        for(int k = left + 1; k <= right; k++){
            if(nums[k] > pivot){
                mid++;
                swap(nums, mid, k);
            }
        }
        swap(nums, mid, left);
        return mid;
    }
    int binaryFind(vector<int>& nums, int left, int right, int target){
        if(left == right){
            if(left == target - 1)
                return left;
            else return -1;
        }
        int p = partition(nums, left, right);
        if(p == target - 1)
            return p;
        if(target - 1 < p){
            int left_p = binaryFind(nums, left, p - 1, target);
            return left_p;
        }
        else{
            int right_p = binaryFind(nums, p + 1, right, target);
            return right_p;
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int index = binaryFind(nums, 0, nums.size() - 1, k);
        return nums[k - 1];
    }
};