Share my C++ solution using Binary Search ,easy to understand


  • 0
    V
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int n = matrix.size();
            int left = matrix[0][0];
            int right = matrix[n-1][n-1];
            int mid = 0;
            int counts = 0;
            
            while (left < right)
            {
                mid = left + ((right - left) >> 1);
                counts = 0;
                
                for (int i = 0; i < n; i++)
                    counts += find_first_greater(matrix[i], n, mid);
                
                if (counts < k)
                    left = mid + 1;
                else
                    right = mid;
            }
            
            return left;
        }
        
        int find_first_greater(vector<int> &array, int size, int key)
        {
            int left = 0;
            int right = size - 1;
            int mid = 0;
            int pos = 0;
            
            if (array[right] <= key)
                return size;
            if (array[left] > key)
                return 0;
                
            while (left < right)
            {
                mid = left + ((right - left) >> 1);
                
                if (array[mid] > key)
                {
                    right = mid;
                    pos = right;
                }
                else
                {
                    left = mid + 1;
                    pos = left;
                }
            }
            
            return pos;
        }
    };
    

Log in to reply
 

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