- 相關推薦
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