b130 - NOIP2006 1.明明的随机数
題目描述
題目要求從輸入的一組整數中移除重複的數字，並將剩下的數字從小到大排序後輸出。首先輸出不重複數字的個數，然後輸出排序後的數字序列。
解題思路
這題的解題思路很直接。首先，讀取輸入的整數個數 N 和 N 個整數。然後，使用嵌套迴圈檢查是否有重複的數字。如果找到重複的數字，將其中一個設為 0，並將不重複數字的計數器減 1。接著，對陣列進行排序。最後，輸出不重複數字的個數和排序後的數字序列，跳過所有為 0 的元素。
複雜度分析
- 時間複雜度: O(n^2 + n log n)，其中 n 是輸入的整數個數。O(n^2) 是來自於嵌套迴圈的重複元素檢查，O(n log n) 是來自於排序。
- 空間複雜度: O(n)，因為我們需要一個陣列
b來儲存輸入的整數。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int a,c;
while(cin >> a){
int b[a];
c=a;
for(int i=0;i<a;i++){
cin >> b[i];
}
for(int i=0;i<a;i++){
for(int j=i+1;j<a;j++){
if(b[i]==b[j]){
b[i]=0;
c--;
}
}
}
sort(b,b+a);
cout << c << endl;
for(int i=0;i<a;i++){
if(b[i]!=0){
cout << b[i] << " ";
}
}
cout << endl;
}
}