d244 - 一堆石頭
題目描述
題目給定一串以空格分隔的正整數，這些數字代表潘潘目前擁有的石頭編號。已知潘潘原本每顆石頭都複製了兩個，然後掉了一顆，因此目前擁有的石頭數量是 3 的倍數減 1。題目要求找出掉落的那顆石頭的編號。
解題思路
解題思路是先將輸入的數字陣列進行排序。由於掉落的石頭原本應該有三個相同的編號，排序後，如果某個編號出現次數少於三次，那麼這個編號就是掉落的石頭。程式碼中，迴圈以三個數字為一組進行檢查，如果發現某組數字不全相同，則輸出該組的第一個數字，即為掉落的石頭編號。
複雜度分析
- 時間複雜度: O(n log n)，主要來自於排序操作。
- 空間複雜度: O(n)，主要來自於儲存輸入數字的陣列。
程式碼
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
int main(){
string a;
while(getline(cin,a)){
int n=1;
for(int i=0;i<a.length();i++){
if(a[i]==' ')
n++;
}
stringstream ss(a);
int b[n];
for(int i=0;i<n;i++)
ss>>b[i];
sort(b,b+n);
for(int i=0;i<n-1;i+=3){
if(b[i]!=b[i+1]||b[i+1]!=b[i+2]){
cout << b[i] << endl;
break;
}
}
}
}