i399 - 1. 數字遊戲

🔗 前往 ZeroJudge 原題

題目描述

題目給定三個介於 1 到 9 之間的整數，要求先輸出眾數的數量，然後輸出去除重複數字後，依大小排序的數字序列。

解題思路

首先，將輸入的數字排序。然後，遍歷排序後的數字，計算每個數字出現的次數。眾數的數量就是出現次數最多的數字的次數。接著，去除重複的數字，並將剩下的數字從大到小排序後輸出。程式碼中，ct 變數用於追蹤重複數字的數量，a 陣列儲存輸入的數字。排序後，透過迴圈移除重複數字，並更新 ct 的值。最後，輸出眾數的數量和排序後的唯一數字。

複雜度分析

• 時間複雜度: O(n log n)，主要來自於 sort 函數的排序操作，其中 n 為輸入數字的個數 (本題為 3)。
• 空間複雜度: O(1)，使用了固定大小的陣列 a，空間使用量不隨輸入大小變化。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a[4]={},ct=0;
	for(int i=0;i<3;++i)
		cin >> a[i];
	sort(a,a+3);
	for(int i=0;i<2-ct;){
		if(a[i]==a[i+1]){
			++ct;
			a[i]=a[i+1];
			a[i+1]=a[i+2];
			a[i+2]=0;
		}
		else{
			++i;
		}
	}
	cout << 1+ct << " ";
	for(int i=2-ct;i>=0;--i)
		cout << a[i] << " ";
}