Problem_2MajorityProblem

NO IMAGE

定義:給定一個大小為 n 的數組,找出其中出現次數超過 n/2 的元素
(常見的面試題)

解決思路:
###Solution 1
一個很常見的想法是先將這組數排序再遍歷,對每個數字做出統計,那麼超過n/2的數字可以直接輸出。
採用效率最高的推排序,最終複雜度為O(nlgn+n)
空間複雜度為O(n)

###Solution 2
從排序中可以知道,最好的排序效果是哈希的O(1),那麼我們可以考慮採用Hash表,以空間換時間的效果得出最優解。
時間複雜度O(1)
空間複雜度O(n)

###Solution 3
Hash的一大問題是對於空間的開銷以及Hash函數的設計,所以在一般條件下S2中的時間複雜度是無法達到O(1)的,因而我們可以在時間上做一個讓步,找到一個O(n)時間,O(1)空間的算法來解決Majority Problem

一個常規的想法是設計兩個臨時變量,在一次遍歷的過程中做增加或者刪減動作。基於的思路是:一個數組中最多隻有兩個數符合要求,通常只有一個數,在一般情況下,對其他非Majority 做統計是非常浪費空間的行為。
那麼對於這個問題的解法我找到了這樣的鏈接以供參考:
http://wdxtub.com/interview/14520595473349.html
Moore投票法代碼如下:

/*----Majority Porblem----------
------Date:2017.9.28------------
------Time:O(n) Space:O(1)-----*/
#include <stdio.h>
#include <stdlib.h>
//Moore 投票法
int find_majority(int* a, int length)
{
int candidate = a[0];
int cnt = 1;
for (int i = 1; i < length; i++)
{
if (cnt == 0)
{
candidate = a[i];
cnt++;
continue;
}
else{
if (candidate == a[i])
cnt++;
else
cnt--;	
}
}
return candidate;
}
int main()
{
int *in, n, i;
scanf("%d",&n);
in = (int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++){
scanf("%d",&in[i]);
}
printf("Majority number is %d\n",find_majority(in,n));
return 0;
}

相關文章

C++期末大作業圖書評論和推薦系統

C++課大作業魔獸世界Part2

數據庫實驗3數據定義語言DDL

網絡身份認證——Kerberos配置及認證