- 相關(guān)推薦
2016年百度實(shí)習(xí)生筆試之乘法表
度度熊和爺爺在玩一個(gè)乘法表游戲。乘法表的第i行第j列位置的元素為i*j，并且乘法表下標(biāo)編號(hào)從1開始，比如2×3乘法表為 1 2 3 2 4 6 爺爺十分聰明，對于n*m的乘法表，只要度度熊給出一個(gè)數(shù)k，爺爺就能立刻告訴度度熊乘法表中元素按照不減順序排列之后，第k個(gè)元素是多少。你能重復(fù)這個(gè)游戲嗎？ 輸入 輸入數(shù)據(jù)是三個(gè)整數(shù)：n, m, k (1≤n, m≤5*105, 1≤k≤nm)。 樣例輸入 2 3 4 輸出 輸出n*m乘法表按照不減順序排列的第k個(gè)數(shù)。 樣例輸出 3 時(shí)間限制 C/C++語言：1000MS其它語言：3000MS 內(nèi)存限制 C/C++語言：65536KB其它語言：589824KB
首先分析這道題目，根據(jù)這個(gè)乘法表，比如乘法表 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 15 18
比如小于等于12的數(shù)的個(gè)數(shù)就是6+12/2+…12/3=16個(gè)，因此對于任意一個(gè)數(shù)，我們可以很容易分析在乘法表中小于等于該數(shù)的數(shù)的個(gè)數(shù)，這樣我們就可以用二分查找了。
但是有一點(diǎn)要注意的是，這個(gè)里面的數(shù)是有重復(fù)的，并不能直接用那種最原始的二分法查找，要有一些小的改進(jìn)，比如上面這個(gè)表中小于等于12的數(shù)有16個(gè)，而要找第15個(gè)數(shù)，按照一般二分查找，又要在小于12的數(shù)里面找了，顯然不對，可以加一個(gè)限制條件，比如小于等于12的數(shù)有16個(gè)，在判斷小于等于11的數(shù)有多少個(gè)？若小于15，則這個(gè)數(shù)就是12。
【百度實(shí)習(xí)生筆試之乘法表】相關(guān)文章：
「09校園招聘」百度筆試題07-12
有關(guān)往年百度筆試真題07-03
關(guān)于百度、騰訊招聘筆試問題07-11
華為筆試題之十五07-11
百度2011.10.16校園招聘會(huì)筆試題07-12
百度校園招聘西安站筆試地點(diǎn)07-12
2015百度上海運(yùn)營筆試經(jīng)驗(yàn)07-01
ebay實(shí)習(xí)生筆試題07-02