問題描述:

?????? 現(xiàn)在有一數(shù)組存放int型整數(shù)，數(shù)字有重復(fù)，且有一數(shù)字出現(xiàn)的頻率超過了50%，請找出這個(gè)數(shù)字。

?????? 補(bǔ)充：主要考慮數(shù)據(jù)量很大的情況。

?

問題求解：

分析：

????? 最直接的方法就是對數(shù)組中所有的數(shù)字排序，然后再掃描一遍，統(tǒng)計(jì)各個(gè)數(shù)字出現(xiàn)的次數(shù)，如果某個(gè)數(shù)字出現(xiàn)的次數(shù)超過一半，則輸出這個(gè)數(shù)字。顯然這個(gè)算法的時(shí)間復(fù)雜度是O(N * log2N + N)。

????? 事實(shí)上，假如現(xiàn)在數(shù)組已經(jīng)有序，那么數(shù)組中間的數(shù)字一定是這個(gè)要求的數(shù)字，所以根本不必掃描。此時(shí)算法的時(shí)間復(fù)雜度是O(N * log2N + 1)。那還能不能再簡化一些呢？

????? 我們看到，算法主要的消耗在排序這塊，那能否跳過排序這個(gè)步驟呢？我們這樣想，假如每次刪除兩個(gè)不同的數(shù)（不管包括不包括最高頻數(shù)），那么，在剩下的數(shù)字里，原最高頻數(shù)出現(xiàn)的頻率一樣超過了50%，不斷重復(fù)這個(gè)過程，最后剩下的將全是同樣的數(shù)字，即最高頻數(shù)。此算法避免的排序，時(shí)間復(fù)雜度只為O(N)。

代碼如下：

?static int FindMostApperse(int[] num)
? ? ? ? {
? ? ? ? ? ? int candidate = 0;
? ? ? ? ? ? int count = 0;
? ? ? ? ? ? for (int i = 0; i < num.Length; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (count == 0)
? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? candidate = num[i];
? ? ? ? ? ? ? ? ? ? count = 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (candidate == num[i])
? ? ? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? count--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return candidate;
? ? ? ? }

?

????? 這個(gè)算法體現(xiàn)了計(jì)算機(jī)科學(xué)中一種很普遍的思想，就是把一個(gè)問題轉(zhuǎn)化為規(guī)模較小的若干個(gè)問題。分治、遞歸、貪心等都是基于這樣的思想。轉(zhuǎn)化的效率越高，轉(zhuǎn)化之后問題的規(guī)模縮小的越快，則正題的時(shí)間復(fù)雜度越低。

?

擴(kuò)展問題：

????? 現(xiàn)在數(shù)組中沒有出現(xiàn)頻率一半的數(shù)字了，但有三個(gè)都超過了四分之一，找到他們。

分析：

????? 與原問題一樣，只要降低規(guī)模即可，每次去掉四個(gè)不相同的數(shù)字，一直重復(fù)，最后剩下的三個(gè)數(shù)字就是答案。

代碼如下：

static int candiA = 0, candiB = 0, candiC = 0;
? ? ? ? static void FindThreeMost(int[] num)
? ? ? ? {
? ? ? ? ? ? int countA = 0, countB = 0, countC = 0;
? ? ? ? ? ? for (int i = 0; i < num.Length; i++)
? ? ? ? ? ? { ? ? ? ? ?
? ? ? ? ? ? ? ? if (countA == 0 || countB == 0 || countC == 0 )
? ? ? ? ? ? ? ? { ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? if (countA == 0)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if (countB != 0 && num[i] == candiB)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countB++;
? ? ? ? ? ? ? ? ? ? ? ? else if (countC != 0 && num[i] == candiC)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countC++;
? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? candiA = num[i];
? ? ? ? ? ? ? ? ? ? ? ? ? ? countA++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else if (countB == 0)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if (countA != 0 && num[i] == candiA)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countA++;
? ? ? ? ? ? ? ? ? ? ? ? else if (countC != 0 && num[i] == candiC)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countC++;
? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? candiB = num[i];
? ? ? ? ? ? ? ? ? ? ? ? ? ? countB++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else if (countC == 0)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if (countA != 0 && num[i] == candiA)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countA++;
? ? ? ? ? ? ? ? ? ? ? ? else if (countB != 0 && num[i] == candiB)
? ? ? ? ? ? ? ? ? ? ? ? ? ? countB++;
? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? candiC = num[i];
? ? ? ? ? ? ? ? ? ? ? ? ? ? countC++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (num[i] == candiA)
? ? ? ? ? ? ? ? ? ? ? ? countA++;
? ? ? ? ? ? ? ? ? ? else if (num[i] == candiB)
? ? ? ? ? ? ? ? ? ? ? ? countB++;
? ? ? ? ? ? ? ? ? ? else if (num[i] == candiC)
? ? ? ? ? ? ? ? ? ? ? ? countC++;
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? countA--;
? ? ? ? ? ? ? ? ? ? ? ? countB--;
? ? ? ? ? ? ? ? ? ? ? ? countC--;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

?

????? 此算法的時(shí)間復(fù)雜度仍為O(N),只是判斷條件較多,歡迎大家拿出更簡明的代碼來討論。

?

?

?

總結(jié)

以上是生活随笔為你收集整理的编程之美系列之二——寻找出现频率超过一半的数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。