[LeetCode]Kth Smallest Number in Multiplication Table

乘法表就是从左向右，自上而下递增的2D matrix。所以我们可以采用和Kth Element in Sorted Matrix一样的解法。也就是值域上的2分法。时间复杂度O(m * log (m * n))，代码如下：

	class Solution {
	public:
	int findKthNumber(int m, int n, int k) {
	int lo = 1, hi = m * n;
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	int i = count(m, n, mid);
	if(i >= k)
	hi = mid;
	else
	lo = mid + 1;
	}
	return lo;
	}
	private:
	int count(int m, int n, int num)
	{
	int i = m, j = 1, res = 0;
	while(j <= n && i > 0)
	{
	while(i * j > num)
	--i;
	res += i;
	++j;
	}
	return res;
	}
	};

view raw Kth Smallest Number in Multiplication Table.cpp hosted with ❤ by GitHub