問題(2013 統考408真題）：已知一個整數序列A = (a0,a1,...,an-1), 其中0≤ai≤n (0≤i<n)，若存在ap1=ap2...=apm=x且m>n/2 (0≤pk≤n，1≤k≤m),則稱x為A的主元素，例如，A=(0，5，5，3，5，7，5，5)，則5為主元素，又如A=(0, 5, 5，3, 5, 1, 5，7)，則A中沒有主元素，假設A中的n個元素保存在一個一維陣列中， 請設計一個盡可能高效的演算法，找出A的主元素，若存在主元素，則輸出該元素:否則輸出-1，
解答：
- 演算法設計思想：從頭掃描陣列，標記可能出現的主元素，最后對該標記的主元素
num計數，確定其是否為主元素， - 步驟：
- 將第一個出現的元素
num保存到c中，用count記錄num出現的次數，初始時令count = 1，如果下一個遇到的元素仍然是num則將count加1，否則將count減1，如果此時count == 0，則將下一個元素保存到c中，并重置count為0，重復上述程序，直至掃描完全部元素， - 判斷此時的
c是否為真正的主元素，統計c出現的次數，并保存到count中，如果count > n / 2，則是主元素，否則不是，
- 將第一個出現的元素
- 演算法的正確性：
- 對于這樣一個序列，去除其中任意兩個不相等的元素，在剩下的元素中，如果存在主元素，主元素出現的次數仍然大于
n / 2， - 使用
count進行計數時，當count == 0時，一定有偶數個的元素與可能的主元素進行了比較，這偶數個元素中一半是可能的主元素，另一半是其他數，
- 對于這樣一個序列，去除其中任意兩個不相等的元素，在剩下的元素中，如果存在主元素，主元素出現的次數仍然大于
- 復雜度：
T(n) = O(n),S(n) = O(1)，
演算法實作：
int Majority(int A[], int n)
{
int i, c, count = 1;
c = A[0];
for (i = 1; i < n; i++)
{
if (A[i] == c)
{
count++;
}
else
{
if (count > 0)
{
count--;
}
else
{
c = A[i];
count = 1;
}
}
}
if (count > 0)
{
count = 0;
for (i = 0; i < n; i++)
{
if (A[i] == c)
{
count++;
}
}
}
if (count > n / 2) return c;
else return -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65478.html
標籤：其他
上一篇：遞回-漢諾塔問題