My thought with binary search


  • 0
    L
    class Solution {
    public:
        int judge(vector<vector<int>>& matrix, int x, int k) {
            int n = matrix.size(), m = matrix[0].size() - 4;
            int sm = 0, nb = 0;
            //printf("x=%d\n", x);
            for(int i = 0; i < n; i++) {
                int l = matrix[i][m], r = matrix[i][m + 1];
                //printf("i=%d, l=%d, r=%d\n", i, l, r);
                // get the number of elements in row i that not smaller than x
                int L = l, R = r, res = l - 1;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if(matrix[i][mid] <= x) {
                        l = mid + 1;
                        res = mid;
                    }
                    else r = mid - 1;
                }
                matrix[i][m + 2] = res;
                nb += res + 1;
                res = L - 1;
                // get the number of elements in row i that smaller than x
                l = L; r = R;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if(matrix[i][mid] < x) {
                        l = mid + 1;
                        res = mid;
                    }
                    else r = mid - 1;
                }
                matrix[i][m + 3] = res;
                sm += res + 1;
                //printf("sm=%d, nb=%d\n", sm, nb);
            }
            if(nb >= k && sm < k) return 0;
            else if(nb < k) {
                for(int i = 0; i < n; i++) {
                    matrix[i][m] = matrix[i][m + 2] + 1;
                }
                return 1;
            }
            else {
                for(int i = 0; i < n; i++) {
                    matrix[i][m + 1] = matrix[i][m + 3];
                }
                return -1;
            }
        }
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int n = matrix.size(), m = matrix[0].size();
            for(int i = 0; i < n; i++) {
                matrix[i].push_back(0);
                matrix[i].push_back(m - 1);
                matrix[i].push_back(0);
                matrix[i].push_back(0);
            }
            int l = matrix[0][0], r = matrix[n - 1][m - 1];
            int ans = 0;
            while(l <= r) {
                int mid = l * 1LL + r >> 1, ret;
                if((ret = judge(matrix, mid, k)) == 0) {
                    ans = mid;
                    break;
                }
                else if(ret == 1) l = mid + 1;
                else r = mid - 1;
            }
            return ans;
        }
    };
    

Log in to reply
 

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