(4月新番)[繁]怪異與	[繁]轉生貴族憑鑑定技	[繁]怪物轉生 Re:Mons
(4月新番)[繁]神明渴	(4月新番)[繁]搖曳露	[繁]戰隊大失格03-

查看: 1919|回復: 8

[教學]一道經典的面試題：二維數組查找[複製鏈接]

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

電梯直達

樓主

發表於 2014-5-15 07:05 PM|只看該作者|倒序瀏覽

如果瀏覽伊莉時速度太慢或無法連接，可以使用其他分流瀏覽伊莉，www01.eyny.com(02,03)。

本帖最後由 kym3 於 2014-5-15 07:06 PM 編輯

這是一道關于二分查找的面試題。

有一個二維數組，每一行都是按從小到大的順序排列的，並且，第一行最大的數小于等于第二行最小的數，第二行最大的數小于等于第三行最小的數。

例如：
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]

...

瀏覽完整內容，請先註冊或登入會員

點評

snowflying 這分類讓我有點掙扎... 發表於 2014-5-15 10:42 PM

經典的

分享0收藏0支持0

若有安裝色情守門員，可用無界、自由門等軟件瀏覽伊莉。或使用以下網址瀏覽伊莉: http://www.eyny.com:81/index.php

使用道具檢舉

snowflying

尊貴會員

Melty Snow　　雪靈

Rank: 6 Rank: 6 Rank: 6 Rank: 6 Rank: 6 Rank: 6

帖子: 3222
積分: 24364 點
潛水值: 77170 米

頭香

發表於 2014-5-15 10:45 PM|只看該作者

若瀏覽伊莉的時侯發生問題或不正常情況，請使用Internet Explorer(I.E)。

先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?

分享使你變得更實在，可以使其他人感到快樂，分享是我們的動力。今天就來分享你的資訊、圖片或檔案吧。

使用道具檢舉

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

3樓

發表於 2014-5-15 11:30 PM|只看該作者

伊莉影片

snowflying 發表於 2014-5-15 10:45 PM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?

對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。...

瀏覽完整內容，請先註冊或登入會員

點評

snowflying 我覺得加上 const 會比較好，所以我的 code 改成 const int target 了發表於 2014-5-16 12:16 AM

如果瀏覽伊莉時速度太慢或無法連接，可以使用其他分流瀏覽伊莉，www01.eyny.com(02,03)。

使用道具檢舉

andrew33673367

高級幼兒生(30/200)

YEE

Rank: 1

帖子: 300
積分: 193 點
潛水值: 11150 米

4樓

發表於 2014-5-15 11:50 PM|只看該作者

如果你忘記伊莉的密碼，請在登入時按右邊出現的 '找回密碼'。輸入相關資料後送出，系統就會把密碼寄到你的E-Mail。

snowflying 發表於 2014-5-15 10:45 PM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?

為甚麼不從第二維中間那行開始找??不是排好了嗎??...

瀏覽完整內容，請先註冊或登入會員

點評

snowflying 所以我才會說找每行的的開頭會比較好發表於 2014-5-16 12:13 AM

andrew33673367 喔了解還有那行有幾個的問題發表於 2014-5-16 12:07 AM

snowflying 要先知道在哪一行吧發表於 2014-5-15 11:56 PM

若瀏覽伊莉的時侯發生問題或不正常情況，請使用Internet Explorer(I.E)。

使用道具檢舉

snowflying

尊貴會員

Melty Snow　　雪靈

Rank: 6 Rank: 6 Rank: 6 Rank: 6 Rank: 6 Rank: 6

帖子: 3222
積分: 24364 點
潛水值: 77170 米

5樓

發表於 2014-5-16 12:11 AM|只看該作者

若登入不正常或變回訪客狀態，請先刪除COOKIE再登入。

本帖最後由 snowflying 於 2014-5-16 01:31 AM 編輯

kym3 發表於 2014-5-15 11:30 PM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。

...

瀏覽完整內容，請先註冊或登入會員

Melty Snow [雪靈]

若瀏覽伊莉的時侯發生問題或不正常情況，請使用Internet Explorer(I.E)。

使用道具檢舉

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

6樓

發表於 2014-5-16 01:52 PM|只看該作者

若瀏覽伊莉的時侯發生問題或不正常情況，請使用Internet Explorer(I.E)。

snowflying 發表於 2014-5-16 12:11 AM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

也可改成

贊！

面試官可能繼續問：“假如不讓用upper_bound和binary_search這兩個函數呢？你能自己把這兩個函數實現一下嗎？”...

瀏覽完整內容，請先註冊或登入會員

分享使你變得更實在，可以使其他人感到快樂，分享是我們的動力。今天就來分享你的資訊、圖片或檔案吧。

使用道具檢舉

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

7樓

發表於 2014-5-16 01:53 PM|只看該作者

所有積分大於負-100的壞孩子，將可獲得重新機會成為懲罰生，權限跟幼兒生一樣。

kym3 發表於 2014-5-15 11:30 PM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。

const可以加在matrix上，加在target上沒有必要，開源代碼中很少有這麼寫的。...

瀏覽完整內容，請先註冊或登入會員

點評

snowflying 可是像 C++ binary_search 第三個參數為 const T& val ，而搜尋使用 const value 感覺也很合理發表於 2014-5-16 02:07 PM

如果重複性登入後自動登出，請先刪除所有Cookie和舊網頁再登入。

使用道具檢舉

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

8樓

發表於 2014-5-16 02:11 PM|只看該作者

回覆中加入附件並不會使你增加積分，請使用主題方式發佈附件。

本帖最後由 kym3 於 2014-5-16 02:12 PM 編輯

kym3 發表於 2014-5-16 01:53 PM
下載: 訪客無法瀏覽下載點，請先註冊或登入會員

const可以加在matrix上，加在target上沒有必要，開源代碼中很少有這麼寫的。

...

瀏覽完整內容，請先註冊或登入會員

上傳頭像立即獲得 1 點積分。

使用道具檢舉

kym3

高級幼兒生(30/200)

Rank: 1

帖子: 126
積分: 87 點
潛水值: 4060 米

9樓

發表於 2014-5-17 06:18 PM|只看該作者

如果你忘記伊莉的密碼，請在登入時按右邊出現的 '找回密碼'。輸入相關資料後送出，系統就會把密碼寄到你的E-Mail。

本帖最後由 kym3 於 2014-5-17 06:21 PM 編輯

bool searchMatrix(vector<vector<int> > &matrix, int target) {
      size_t m=matrix.size();
      size_t begin=0;
      for(;m;m>>=1){
         size_t mid=begin+ (m>>1);
         if(matrix[mid][0]<=target){
...

瀏覽完整內容，請先註冊或登入會員

回覆中加入附件並不會使你增加積分，請使用主題方式發佈附件。

使用道具檢舉

返回列表

Archiver|手機版|廣告|聯絡我們|廣告查詢|廠商合作|伊莉

GMT+8, 2024-4-29 10:19 AM

重要聲明：本討論區是以即時上載留言的方式運作，對所有留言的真實性、完整性及立場等，不負任何法律責任。而一切留言之言論只代表留言者個人意見，並非本網站之立場，用戶不應信賴內容，並應自行判斷內容之真實性。於有關情形下，用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。由於本討論區受到「即時上載留言」運作方式所規限，故不能完全監察所有留言，若讀者發現有留言出現問題，請聯絡我們。有權刪除任何留言及拒絕任何人士上載留言，同時亦有不刪除留言的權利。切勿上傳和撰寫侵犯版權(未經授權)、粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論，敬請自律。本網站保留一切法律權利。