Kattis - Odd Man Out
題目
https://open.kattis.com/problems/oddmanout
有
對於每一筆測試資料,保證只有一個數字只出現過奇數次,求該數字為何
想法
對於無序的資料,我們可以觀察看看排序之後有沒有特殊的性質可以使用
在這邊我們發現到,當我們將這群數字由小到大排序之後,一樣的數字都會聚集在同一個區域
如此一來,我們就可以直接搜尋過這些相同數字的區域,如果數字個數為奇數,那麼就找到了答案
更進一步的說,我們的步驟會是
- 輸入資料
- 將資料由小到大排序
- 從第
個元素開始,每次檢查上一個元素跟自己是否相同- 相同
將計數器 - 不相同
檢查計數器是奇數或是偶數- 奇數
找到答案輸出 - 偶數
將計數器重整
- 奇數
- 相同
Code
1 | //By Koios1143 |
複雜度分析
輸入的時間複雜度為
排序的時間複雜度為
搜尋答案的時間複雜度為
總時間複雜度
未找到相關的 Issues
請聯絡 @Koios1143 初始化評論