百度实习生笔试之乘法表

2016年百度实习生笔试之乘法表

　　度度熊和爷爷在玩一个乘法表游戏。乘法表的第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 时间限制 C/C++语言：1000MS其它语言：3000MS  内存限制 C/C++语言：65536KB其它语言：589824KB

　　首先分析这道题目，根据这个乘法表，比如乘法表 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 15 18

　　比如小于等于12的数的个数就是6+12/2+…12/3=16个，因此对于任意一个数，我们可以很容易分析在乘法表中小于等于该数的数的个数，这样我们就可以用二分查找了。

　　但是有一点要注意的是，这个里面的数是有重复的，并不能直接用那种最原始的二分法查找，要有一些小的改进，比如上面这个表中小于等于12的数有16个，而要找第15个数，按照一般二分查找，又要在小于12的数里面找了，显然不对，可以加一个限制条件，比如小于等于12的数有16个，在判断小于等于11的数有多少个？若小于15，则这个数就是12。

【百度实习生笔试之乘法表】相关文章：

「09校园招聘」百度笔试题07-12

有关往年百度笔试真题07-03

百度产品运营岗笔试题12-15

百度产品经理笔试题目06-25

关于百度、腾讯招聘笔试问题07-11

华为笔试题之十五07-11

百度2011.10.16校园招聘会笔试题07-12

百度校园招聘西安站笔试地点07-12

2015百度上海运营笔试经验07-01

ebay实习生笔试题07-02