binary search C++ solution


  • 0
    Y
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int low = matrix[0][0];
            int high = matrix.back().back();
            int kcount{0};
            while(low<high) {
                int count{0};
                int med = (low + high)/2;
                for(auto &v:matrix){
                    auto it = upper_bound(begin(v), end(v), med);
                    count += it - begin(v);
                }
                if(count < k) {
                    kcount+=count;
                    low = med+1;
                } else {
                    high = med;
                }
            }
            return low;
        }
    

Log in to reply
 

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