Leetcode.378.Kth Smallest Elemen

题目

给定一个二维数组, 数组的每行每列都是递增的, 找到倒数第k小的数.

Input: [[ 1,  5,  9],[10, 11, 13],[12, 13, 15]], k = 8
Output: 13

思路

采用二分法, 先找到中间大小的数, 然后找出该数的位置, 不断更新中间数的大小.

int kthSmallestHelper(vector<vector<int>>& matrix,int& x) {
    int n = (int)matrix.size();
    int res = 0;
    for(int i=0; i<n; i++) {
        res += upper_bound(matrix[i].begin(), matrix[i].end(), x) - matrix[i].begin();
    }
    return res;
}

int kthSmallestHelper2(vector<vector<int>>& matrix,int& x) {
    int n = (int)matrix.size();
    int res = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if (matrix[i][j] <= x) {
                res++;
            }
        }
    }
    return res;
}

int kthSmallestHelper3(vector<vector<int>>& matrix,int& x) {
    int n = (int)matrix.size();
    int res = 0;

    int i = 0,j = 0;

    while(x > matrix[i][n-1]) {
        res += n;
        i++;
    }
    while(x > matrix[n-1][j]) {
        res += n-i;
        j++;
    }
    for(; i<n; i++) {
        for(int k = j; k<n; k++) {
            if (matrix[i][k] <= x) {
                res++;
            }
        }
    }
    return res;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    if (matrix.empty()) return 0;

    int n = (int)matrix.size();
    int low = matrix[0][0];
    int high = matrix[n-1][n-1];

    while (low < high) {
        int mid = (low + high) / 2;
        int pos = kthSmallestHelper(matrix, mid);
        cout << " " << mid << " | "<< pos << " " ;
        if (pos < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    cout  << endl ;
    return low;
}

总结

upper_bound和lower_bound可以找出某个数在数组中的位置.

vec = [10 20 30 30 20 10 10 20]
lower_bound(vec.begin(), vec.end(),20);  // 1 
upper_bound(vec.begin(), vec.end(),20); // 8