2016年百度實習(xí)生筆試之乘法表

　　度度熊和爺爺在玩一個乘法表游戲。乘法表的第i行第j列位置的元素為i*j，并且乘法表下標編號從1開始，比如2×3乘法表為 1 2 3 2 4 6 爺爺十分聰明，對于n*m的乘法表，只要度度熊給出一個數(shù)k，爺爺就能立刻告訴度度熊乘法表中元素按照不減順序排列之后，第k個元素是多少。你能重復(fù)這個游戲嗎？ 輸入 輸入數(shù)據(jù)是三個整數(shù)：n, m, k (1≤n, m≤5*105, 1≤k≤nm)。 樣例輸入 2 3 4 輸出 輸出n*m乘法表按照不減順序排列的第k個數(shù)。 樣例輸出 3 時間限制 C/C++語言：1000MS其它語言：3000MS  內(nèi)存限制 C/C++語言：65536KB其它語言：589824KB

　　首先分析這道題目，根據(jù)這個乘法表，比如乘法表 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 15 18

　　比如小于等于12的數(shù)的個數(shù)就是6+12/2+…12/3=16個，因此對于任意一個數(shù)，我們可以很容易分析在乘法表中小于等于該數(shù)的數(shù)的個數(shù)，這樣我們就可以用二分查找了。

　　但是有一點要注意的是，這個里面的數(shù)是有重復(fù)的，并不能直接用那種最原始的二分法查找，要有一些小的改進，比如上面這個表中小于等于12的數(shù)有16個，而要找第15個數(shù)，按照一般二分查找，又要在小于12的數(shù)里面找了，顯然不對，可以加一個限制條件，比如小于等于12的數(shù)有16個，在判斷小于等于11的數(shù)有多少個？若小于15，則這個數(shù)就是12。

【百度實習(xí)生筆試之乘法表】相關(guān)文章：

「09校園招聘」百度筆試題07-12

有關(guān)往年百度筆試真題07-03

百度產(chǎn)品運營崗筆試題12-15

百度產(chǎn)品經(jīng)理筆試題目06-25

關(guān)于百度、騰訊招聘筆試問題07-11

華為筆試題之十五07-11

百度2011.10.16校園招聘會筆試題07-12

百度校園招聘西安站筆試地點07-12

2015百度上海運營筆試經(jīng)驗07-01

ebay實習(xí)生筆試題07-02