c++ beats 99% binary search


  • 0
    Y
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int N = matrix.size();
            int s = matrix[0][0], e = matrix[N - 1][N - 1];
            while(s < e){
                int m = (s + e) / 2;
                int cnt = count(matrix, m);
                // cout << "m: " << m << " cnt: " << cnt << endl;
                if(cnt <= k - 1)
                    s = m + 1;
                else
                    e = m;
            }
            return s;
        }
    
        int count(vector<vector<int>>& matrix, int target){
            int N = matrix.size(), ans = 0;
            for(int i = 0; i < N; i++){
                // cout << "i: " << i << " target: " << target << " v: " << upper(matrix[i], target) << endl;
                ans += upper(matrix[i], target);
            }
            return ans;
        }
    
        int upper(vector<int>& nums, int target){
            int s = 0, e = nums.size() - 1;
            while(s < e){
                int m = (s + e) / 2;
                if(nums[m] > target)
                    e = m;
                else
                    s = m + 1; 
            }
            if(nums[s] <= target)
                return nums.size();
            else
                return s;
        }
    };
    

Log in to reply
 

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