Kattis - Odd Man Out

題目

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

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

$1 \leq N \leq 50 \quad 0 < C < 2^{31} \quad 3 \leq G \leq 1000$

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

想法

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

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

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

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

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

Code

//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)$