切換
舊版
前往
大廳
主題

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

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

題目連結:


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

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


範例輸入:
第一筆輸入:
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


範例輸出:
第一筆輸出:
yes [1, 1]
yes [2, 1]
no

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


解題思維:
將這 n × m 個數字放進同一個一維陣列,並對其排列。(但是要保存每個數字本來在的行列數)

接著就只是對每一筆的詢問做二分搜尋即可。

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

創作回應

胖胖貓
這天看到 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
也是轉45度後視為二元樹做搜尋。
2019-09-27 09:33:03

更多創作