Kattis - Odd Man Out

Kattis - Odd Man Out

題目

https://open.kattis.com/problems/oddmanout

N 筆測試資料,每筆測試資料包含一個數字 G 以及 G 個數字 C

1N500<C<2313G1000

對於每一筆測試資料,保證只有一個數字只出現過奇數次,求該數字為何

想法

對於無序的資料,我們可以觀察看看排序之後有沒有特殊的性質可以使用

在這邊我們發現到,當我們將這群數字由小到大排序之後,一樣的數字都會聚集在同一個區域

如此一來,我們就可以直接搜尋過這些相同數字的區域,如果數字個數為奇數,那麼就找到了答案

更進一步的說,我們的步驟會是

  1. 輸入資料
  2. 將資料由小到大排序
  3. 從第 1 個元素開始,每次檢查上一個元素跟自己是否相同
    • 相同
      將計數器 +1
    • 不相同
      檢查計數器是奇數或是偶數
      • 奇數
        找到答案輸出
      • 偶數
        將計數器重整

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n, m, out;
cin>>n;
for(int Case=1 ; Case<=n ; Case++){
cin>>m;
int arr[1005];
for(int i=0 ; i<m ; i++){
cin>>arr[i];
}

sort(arr, arr+m);

// for 迴圈去檢查跟上一個元素是否相同
// cnt 要先算上第 0 個元素
for(int i=1, cnt=1 ; i<=m ; i++){
if(arr[i] == arr[i-1]) cnt++;
else{
if(cnt%2 != 0){
out = arr[i-1];
break;
}
else{
// cnt 要先算上第 i 個元素
cnt=1;
}
}
}
cout<<"Case #"<<Case<<": "<<out<<"\n";
}
return 0;
}

複雜度分析

輸入的時間複雜度為 O(n)

排序的時間複雜度為 O(nlogn)

搜尋答案的時間複雜度為 O(n)

總時間複雜度 O(n+nlogn)

未找到相關的 Issues

請聯絡 @Koios1143 初始化評論