csp試題2：數字排序

• • 題目
  • 分析
  • 代碼
  • 總結

題目

問題描述

      給定n個整數，請統計出每個整數出現的次數，按出現次數從多到少的順序輸出。

輸入格式

      輸入的第一行包含一個整數n，表示給定數字的個數。

      第二行包含n個整數，相鄰的整數之間用一個空格分隔，表示所給定的整數。

輸出格式

      輸出多行，每行包含兩個整數，分别表示一個給定的整數和它出現的次數。按出現次數遞減的順序輸出。如果兩個整數出現的次數一樣多，則先輸出值較小的，然後輸出值較大的。

樣例

輸入：

12
5 2 3 3 1 3 4 2 5 2 3 5
           

輸出：

3 4
2 3
5 3
1 1
4 1
           

評測用例規模與約定

      1 ≤ n ≤ 1000，給出的數都是不超過1000的非負整數。

分析

      首先建立一個Numbers結構體，這個結構體包含數字（num）和次數（times），num用來儲存對應的數字，times用來儲存對應數字出現的次數。

      接收資料結束後結構體數組numArr[ ]中就包含了輸入資料中所有的數字及每個數字對應出現的次數。接下來我們隻需要在numArr[ ]中找到times最大且對應num最小的資料，然後輸出即可。

代碼

/*
20190910
ccf試題2：數字排序 
*/ 

#include <iostream>
using namespace std;

//建立 數字結構體（數字數值 和 該數字出現的次數） 
struct Numbers{
	int num;	//數字的數值 
	int times;	//該數字出現的次數 
};

Numbers numArr[1000]; 
int length = 0;

int main(){
	//接收資料
	int n;
	cin >>n;
	int temp;
	for(int i=0; i<n; i++){
		cin >>temp;
		//是否是重複數字 
		bool repeat = false;
		for(int j=0; j<length; j++){
			if(temp == numArr[j].num){
				numArr[j].times++;
				repeat = true;
				break; 
			}
		}
		//不是則添加到後面 
		if(!repeat){
			numArr[length].num = temp;
			numArr[length].times = 1;
			length++;
		}
	}	
	
	//依據times輸出
	for(int i=0; i<length; i++){
		int min_num;
		int max_times = 0;
		int index;
		
		//找出出現次數最多且數值最小的數字，并将其times置為-1，以避免再次輸出 
		for(int j=0; j<n; j++){
			if(max_times < numArr[j].times){
				max_times = numArr[j].times;
				min_num = numArr[j].num;
				index = j;
			}
			else if(max_times == numArr[j].times){
				if(min_num > numArr[j].num){
					min_num = numArr[j].num;
					index = j;
				}
			}
		}
		numArr[index].times = -1;
		
		cout<<min_num <<" "<<max_times<<endl; 
	} 
	
	return 0;
} 
           

總結

      這個試題2還是相對較簡單的。細心地你可能還會發現這個題與ccf試題1:出現次數最多的數有相似之處。