题目大意：给出一个矩阵，矩阵下标是从1开始计数，矩阵中的值由下标相乘得到（i*j）。任意给出一个数k，能快速找到矩阵经过排序后对应的第k个数。
解题思路：通过二分查找来确定数字k所在的位置。在每次二分查找中判断中间值 (mid) 和每一行最后一列数值的大小 (i*m)，累加(m)或(mid/i)，i表示行数。用累加和来判断与k的大小。
package 百度; import java.util.Scanner; /** * 题目描述 度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为i*j，并且乘法表下标编号从1开始，比如2 × 3乘法表为 * 1 2 3 * 2 4 6 * 爷爷十分聪明，对于n*m的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？ * * 输入： 输入数据是三个整数：n, m, k (1≤n, m≤5*105, 1≤k≤nm)。 * 样例输入 2 3 4 * 输出：n*m乘法表按照不减顺序排列的第k个数。 样例输出 3 * * 解题思路： * * @author 崔洪振367 * @version 创建时间：2017年5月5日 下午5:05:04 */ public class Q2016实习_乘法表 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { long n = sc.nextLong();// i，行 long m = sc.nextLong();// j，列 long k = sc.nextLong(); long left = 1; long right = n * m;//样例：2*3 long mid = right / 2;//mid为6/2=3,中间位置的数字应该是3 while (left <= right) { mid = (left + right) / 2; long sum = 0; for (int i = 1; i <= n; i++) { long temp = (mid >= i * m) ? m : mid / i;//判断mid和每一行的最后一个数的大小 sum += temp; } if (sum < k) { left = mid + 1; } else { right = mid - 1; } } System.out.println(left); } sc.close(); } }