C++, binary search


  • 1
    R

    This is essentially the same problem as 378. Kth Smallest Element in a Sorted Matrix; the solution for this problem is simpler (and faster) due to the property that each row or column is an arithmetic sequence. The complexity can be optimized to O(min(m,n)log(mn)):

    int findKthNumber(int m, int n, int k)
    {
        int low = 1, high = m * n;
        
        while(low < high)
        {
            int count = 0;
            int mid = (low + high) / 2;
    
            if(m < n)            
            {    
                for(int i = 1; i <= m; i++)
                {
                    count += min(mid / i, n);
                }
            }
            else
            {
                for(int i = 1; i <= n; i++)
                {
                    count += min(mid / i, m);
                }                
            }
            
            if(count < k)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }
        
        return low;
    }

Log in to reply
 

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