演算法初階・雙指標與排序後處理
利用資料已排序:原地去重、左右指標湊預算、兩份清單找交集。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
已排序事件編號去重
容易雙指標訊息佇列「至少送達一次」,消費端收到的事件編號已由小到大排序,但同一個事件可能被送了好幾次。請原地去重:把不重複的編號依序搬到 list 的前段。
輸入:一行,由小到大排序的事件編號(整數,以空白分隔,至少一筆)
輸出:兩行
第 1 行:不重複的事件數 k
第 2 行:去重後的編號(list 前 k 個),以空白分隔
要求:用「寫入位置」與「讀取位置」兩個指標在同一個 list 上完成,不要用 set,也不要另外建新的 list。
範例輸入:
7 7 8 9 9
範例輸出:
3
7 8 9
類型對應:LeetCode「Remove Duplicates from Sorted Array」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
已排序報價湊預算
容易雙指標採購要從報價清單挑兩個不同的品項,價格加起來剛好等於預算。報價已由小到大排序,而且每個價格都不同。
輸入:
第 1 行:預算 budget
第 2 行:由小到大排序的價格(整數,以空白分隔,彼此不同)
輸出:一行
較低價 較高價;有多組時,取「較低價」最小的那一組;找不到印NONE。要求:用左右兩個指標往中間走(一次走完),不要兩層迴圈試所有組合。
範例輸入:
90
15 30 45 60 75
範例輸出:
15 75
類型對應:LeetCode「Two Sum II - Input Array Is Sorted」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
兩系統共同主鍵
容易雙指標對帳時要找出「兩個系統都有」的客戶編號。兩個系統各匯出一份已由小到大排序的客戶編號,每份清單內沒有重複。
輸入:
第 1 行:系統 A 的客戶編號(整數,已排序,以空白分隔;沒有資料時是空行)
第 2 行:系統 B 的客戶編號(格式同上)
輸出:一行,兩邊都有的客戶編號由小到大、以空白分隔;沒有共同的印
NONE。要求:利用兩份都已排序,用兩個指標一次走完,不要用 set,也不要對 A 的每一筆去 B 裡面搜尋。
範例輸入:
3 8 12 20
1 8 20 25
範例輸出:
8 20
類型對應:LeetCode「Intersection of Two Arrays」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了