劍指Offer——陣列中出現次數超過一半的數字

NO IMAGE

題目描述

陣列中有一個數字出現的次數超過陣列長度的一半,請找出這個數字。例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}。由於數字2在陣列中出現了5次,超過陣列長度的一半,因此輸出2。如果不存在則輸出0。

方法一

最先想到的是對陣列記性排序,然後遍歷陣列找出出現次數超過陣列長度的一半的數。該方法的時間複雜度就是排序用的時間,即最快的排序演算法的時間複雜度O(nlogn)。

class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if( numbers.empty() )
return 0;
sort(numbers.begin(),numbers.end());
int i = 0;
int size = numbers.size();
for( int j=0;j<size;j   )
{
if( numbers[j] != numbers[i] )
i = j;
if( j-i 1 > size/2 )
return numbers[j];
}
return 0;
}
};

如果一個數字出現的次數超過陣列長度的一半,那麼在排序後,這個數字應該位於陣列的中間位置,所以可以在對陣列進行排序後,直接取中間位置的數字,但需要考慮不存在出現的次數超過陣列長度的一半的數字的情況,所以在取中間位置的數字後,需要遍歷一遍統計其出現次數進行檢驗。(改進:也可以利用快排思想,利用遞迴找到處於陣列中間位置的數字,而不需要對整個陣列排序排序完)

class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
sort(numbers.begin(), numbers.end());
int size = (int)numbers.size();
int num = numbers[size/2];
int count = 0;
for(int i=0; i<size;   i)
{
if(num == numbers[i])
count;
}
if(count > size/2)
return  num;
else
return  0;
}
};

方法二

利用map記錄每個數字以及數字出現的次數,其中key為陣列元素值,value為此數出現的次數。遍歷一遍陣列,統計每個數出現的次數,判斷有沒有出現次數超過陣列長度的一半的值。此時的時間複雜度為 O(n),空間複雜度為O(n)。個人比較喜歡這種方法,實現起來簡單,不過空間複雜度大一些。

class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if( numbers.empty() )
return 0;
int size = numbers.size();
unordered_map<int, int> record;
for( int i=0;i<size;i   )
{
record[numbers[i]]  ;
if( record[numbers[i]] > size/2 )
return numbers[i];
}
return 0;
}
};

方法三

        如果一個數字出現的次數超過陣列長度的一半,所以這個數字出現的次數比其他數出現的次數的總和還多。考慮每次刪除兩個不同的數,那麼在剩下的數中,出現的次數仍然超過總數的一般,不斷重複該過程,排除掉其他的數,最終找到那個出現次數超過一半的數字。這個方法的時間複雜度是O(N),空間複雜度是O(1)。

       換個思路,這個可以通過計數實現,而不是真正物理刪除。在遍歷陣列的過程中,儲存兩個值,一個是陣列中數字,一個是出現次數。當遍歷到下一個數字時,如果這個數字跟之前儲存的數字相同,則次數加1,如果不同,則次數減1。如果次數為0,則儲存下一個數字並把次數設定為1,由於我們要找的數字出現的次數比其他所有數字出現的次數之和還要多,如果存在,那麼要找的數字肯定是最後一次把次數設為1時對應的數字。

注意:找到數字後需要檢驗其正確性。

class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if( numbers.empty() )
return 0;
int times = 0;
int res = 0;
int size = numbers.size();
for( int i=0;i<size;i   )
{
if( times == 0 )
{
res = numbers[i];
times   ;
}
else if( numbers[i] == res )
times  ;
else
times--;
}
times = 0;
for( int i=0;i<size;i   )
if( numbers[i] == res )
times  ;
if( times > size/2 )
return res;
else
return 0;
}
};