clear java solution! fastest!


  • 0
    Y

    Binary Search within a range [Accepted]

    Intuition

    1. if (m > n), we can transpose the multiplication table, of which the result doesn't change. So we can always deal with a multiplication table with n >= m.

    2. Consider a function int countUnder(int m, int n, int target), which counts the number of numbers in a m * n multiplication table that is less than or equal to target.
      Note:

    • target can be any non-negative integer, which may not be in the multiplication table
    • if target is a number in the multiplication table, then countUnder(m, n, target) > countUnder(m, n, target - 1). But if target is not in the multiplication table, then countUnder(m, n, target) = countUnder(m, n, target - 1).
    1. Now we only need to find a number kthNumber, s.t. countUnder(m, n, kthNumber) >= k > countUnder(m, n, kthNumber - 1), then kthNumber is the largest k-th number we want to find.

    2. Actually, we can deduce the for analytical representation of the function int countUnder(int m, int n, int target) and then derive a range for kthNumber. The detailed process is in the attachment. [0_1504103360984_derivation.pdf](Uploading 100%)
      After getting the range, we can use binary search to get the kthNumber.

    algorithm

    class Solution {
    	static int countUnder(int m, int n, int target) {
    		int l = target / n;
    		int result = l * n;
    		for(int i = l + 1; i <= m; i += 1) {
    			result += target / i;
    		}
    		return result;
    	}
    
    	public int findKthNumber(int m, int n, int k) {
    		// if m > n, we transpose the table, which doesn't change the result
    		// So we can assure that m <= n
    		if(m > n) {
    			int a = m;
    			m = n;
    			n = a;
    		}
    
    		// the kth largest number we want to find
    		int kthNumber = 0;
    		// find l, s.t. l < double(kthNumber) / n <= l + 1
    		// using binary search
    		int l = 0; 
    		int start = 0;
    		int end = m - 1;
    		while(start < end) {
    			int middle = (start + end) / 2;
    			int nums = countUnder(m, n, (middle + 1) * n);
    			if(k <= nums)
    				end = middle;
    			else 
    				start = middle + 1;
    		}
    		// now start == end
    		l = start;
    
    		// calculate the range that the k-th largest number can be in
    		double aux = 0.0;
    		for(int i = l + 1; i <= m; i += 1) {
    			aux += 1.0 / i;	
    		}
    		int min = (int)Math.ceil((k - n * l) / aux);
    		// a trick, (int)Math.ceil(a - 1) = a - 1 if a = integer
    		//                                = (int) a, if a not integer
    		int max = (int)Math.ceil((k - n * l + m - l) / aux - 1); 
    
    		// using binary search to find the k-th largest number
    		start = Math.max(min, n * l + 1);
    		end = Math.min(max, n * (l + 1));
    		while(start < end) {
    			int middle = (start + end) / 2;
    			if(k <= countUnder(m, n, middle))
    				end = middle;
    			else
    				start = middle + 1;
    		}
    		// now start == end
    		kthNumber = start;
    		return kthNumber
    	}
    
    

    Complexity Analysis

    • Time Complexity: O(min(m, n) * log(min(m,n)))
    • Space Complexity: O(1)

Log in to reply
 

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