ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e095: Emilia's story - 1 Extremely search 解題心得

Not In My Back Yard | 2019-03-12 00:02:18 | 巴幣 0 | 人氣 118

題目連結(jié):


題目大意:
給定兩正整數(shù) n 、 m (1 ≦  n 、m  ≦ 1, 600),接著便給定 n × m 個(gè) int 可容納的整數(shù)值。其為 n × m 的陣列。其為由上至下遞增、由左至右也遞增。

接著給定一正整數(shù) q (1 ≦ q ≦ 100, 000),代表有 q 筆詢問(wèn)。每筆詢問(wèn)有一正整數(shù) q。問(wèn) q 是否在此 n × m 之矩陣之中。在的話,問(wèn)在第幾列第幾行。


範(fàn)例輸入:
第一筆輸入:
2 4
1 2 3 4
10 12 20 100
3
1
10
30

第二筆輸入:
5 2
1 10
4 11
12 20
30 33
45 92
3
1
10
2


範(fàn)例輸出:
第一筆輸出:
yes [1, 1]
yes [2, 1]
no

第二筆輸出:
yes [1, 1]
yes [1, 2]
no


解題思維:
將這 n × m 個(gè)數(shù)字放進(jìn)同一個(gè)一維陣列,並對(duì)其排列。(但是要保存每個(gè)數(shù)字本來(lái)在的行列數(shù))

接著就只是對(duì)每一筆的詢問(wèn)做二分搜尋即可。

此次分享到此為止,如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方,也煩請(qǐng)各位大大撥冗討論。

創(chuàng)作回應(yīng)

胖胖貓
這天看到 Leetcode 相同題目的題解:
https://medium.com/@desolution/%E5%BE%9Eleetcode%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-56-binary-search-3-bd76049f8765
也是轉(zhuǎn)45度後視為二元樹(shù)做搜尋。
2019-09-27 09:33:03
追蹤 創(chuàng)作集

作者相關(guān)創(chuàng)作

更多創(chuàng)作