牛客網NC22222:超半的數

題目描述

輸入輸出格式

輸入格式：

• 第一行包含一個整數 n (1 ≤ n ≤ 1000)
• 第二行包含 n 個整數 a_i (1 ≤ a_i ≤ 10^9)

輸出格式：

• 輸出一個整數，表示出現次數超過一半的那個數

解題思路

這道題目有多種解法，本文實現的是最直觀的暴力解法。我們對數組中的每個元素，統計它在數組中出現的次數，如果發現某個元素出現次數超過 n/2，則輸出該元素并結束程序。

算法流程

1. 讀取數組大小 n 和數組元素
2. 對于數組中的每個元素 a[i]：
   • 統計 a[i] 在整個數組中出現的次數
   • 如果出現次數大于 n/2，則輸出 a[i] 并結束程序

復雜度分析

• 時間復雜度：O(n2)，其中 n 是數組大小。我們需要遍歷數組中的每個元素，然后對每個元素再次遍歷數組統計頻次。
• 空間復雜度：O(n)，用于存儲輸入數組。

代碼實現

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;int a[n];// 讀取數組元素for(int i=1;i<=n;i++){cin>>a[i];}// 尋找出現次數超過一半的元素for(int i=1;i<=n;i++){int s=0;//每次外層循環遍歷新元素 a[i] 時，會重新聲明并初始化 s=0，確保統計該元素的出現次數時計數器 s 是從零開始累加的for(int j=1;j<=n;j++){if(a[i]==a[j])s++;}if(s>n/2){cout<<a[i];break;}}return 0;
}

示例解析

以示例 1 為例：

輸入：
5
1 2 2 3 2輸出：
2

執行過程：

1. 讀取 n=5，數組為 [1,2,2,3,2]
2. 對于 a[1]=1，統計出現次數為 1，不超過 5/2=2
3. 對于 a[2]=2，統計出現次數為 3，超過 5/2=2
4. 輸出 2 并結束程序

優化思路

雖然本題的暴力解法已經能夠解決問題，但當數據規模增大時，可能會超時。以下是一些可能的優化方向：

1. 哈希表計數：使用哈希表統計每個元素出現的次數，將時間復雜度降至 O(n)
2. 摩爾投票算法：專門用于找出出現次數超過一半的元素，時間復雜度為 O(n)，空間復雜度為 O(1)

---

注：根據題目要求，本文僅對原有解法進行分析和講解，未對算法本身進行優化。