算法--找出數組中出現次數超過一半的數 作者：陳太漢

算法--找出數組中出現次數超過一半的數

     每當我看到經典的算法題，就懷念高中，感覺很多算法題就是高中的題目，誰叫哥隻讀了個專科，高數基本相當沒學。

     有空要看看高數啊，想當年數學那是相當的......

#include <iostream>

using namespace std;

class FindTheOne

{

public:

  方法一

  第一個想到的方法是見一個二維數組，一維存數組中的資料，二維存這個數出現的次數。出現次數最多的那個數就是要找的那個數

  由于某個數出現的次數超過數組長度的一半，是以二維數組的長度隻需要這個數組的一半。代碼實作如下，

  當然這個方法很糟糕，時間複雜度和空間複雜度都比較大，想練手的我還是寫了一下。

　　

方法一

方法二

     将數組排序，最中間的那個數就是您要找的數。

     如果出現最多的那個數是最小的，那麼1至(n+1)/2都是那個數

     如果出現最多的那個數是最大的，那麼(n-1)/2至n都是那個數

     如果不是最小也不是最大，當這個數由最小慢慢變成最大的最大的數時，你會發現中間的那個數的值是不變的。

     綜上所述，中間的那個數就是你要找的那個數。

 方法三

     這個方法借用了别人的思路。

     在這裡我做一下簡單的分析。

     這個算法的時間複雜度是O(n)，另外用了兩個輔助變量。

     k用于臨時存儲數組中的資料，j用于存儲某個數出現的次數。

     開始時k存儲數組中的第一個數,j為0，如果數組出現的數于k相等，則j加1，否則就減1，如果j為0，就把目前數組中的數賦給k

     因為指定的數出現的次數大于數組長度的一半，所有j++與j--相抵消之後，最後j的值是大于等于1的，k中存的那個數就是出現最多的那個數。

    下面這個算法隻适合數組中數組中某個數的出現次數超過數組長度一半的數組，符合題意。

<a></a>

int Search(int A[],int len)

if(NULL==A || len&lt;=0)

return-1;

}

int k, j=0;

for(int i=0;i&lt;len;++i)

if(j==0)

k=A[i];

if(k==A[i])

++j;//有人說++j比j++有先天的優勢，不知你是否聽說，如果你也聽說，有沒有想過More Effective C++(C++程式員必看書籍)

}else

--j;

return k;

};

本文轉自啊漢部落格園部落格，原文連結：http://www.cnblogs.com/hlxs/archive/2011/06/29/2093517.html