題目描述 牛客網(wǎng)

• 數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字
• 例如，輸入一個長度為 9 的數(shù)組 {1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0

題目解讀

• 劍指Offer 205
• 思路一、基于 Partition 函數(shù)的時間復(fù)雜度為 O(n) 的算法
• 思路二、基于數(shù)組特點找出時間復(fù)雜度為 O(n) 的算法
• 思路三、map 實現(xiàn)。key存儲數(shù)字，value存儲次數(shù)，出現(xiàn)次數(shù)超過數(shù)組長度的一半則找到數(shù)字

代碼

• 思路一、基于 Partition 函數(shù)的時間復(fù)雜度為 O(n) 的算法
  考慮數(shù)組的特性：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半。如果把這個數(shù)組排序，那么排序之后位于數(shù)組中間的數(shù)字一定就是那個出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)組。
  這種算法受到快速排序的啟發(fā)

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int Paritition1(vector<int>& numbers, int left, int right){
        int pivot = numbers[left];
        while(left < right){

            while(left < right && numbers[right] >= pivot){
                right --;
            }
            numbers[left] = numbers[right];

            while(left < right && numbers[left] <= pivot){
                left ++;
            }
            numbers[right] = numbers[left];
        }
        numbers[left] = pivot;
        return left;
    }

    bool checkVality(vector<int> numbers, int result){
        bool vality = true;
        int times = 0;
        int len = numbers.size();
        for(int i=0; i < len; i++){
            if(result == numbers[i]){
                times ++;
            }
        }

        if(times * 2 <= len){
            vality = false;
        }
        return vality;
    }

    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        if(numbers.size() == 0){
            return 0;
        }

        int middle = numbers.size() >> 1;
        int left = 0;
        int right = numbers.size() - 1;
        int pivot = Paritition1(numbers, left, right);

        while(pivot != middle){
            if(pivot > middle){
                right = pivot - 1;
            }
            else{
                left = pivot + 1;
            }
            pivot = Paritition1(numbers, left, right);
        }

        int result = numbers[middle];
        if(!checkVality(numbers, result)){
            result = 0;
        }
        return result;
    }
};

int main(){
    int a[10] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    int len = 9;
    vector<int> numbers;
    Solution ss;

    for(int i=0; i < len; i++){
        numbers.push_back(a[i]);
    }
    cout<<ss.MoreThanHalfNum_Solution(numbers)<<endl;
}

• 思路二、基于數(shù)組特點找出時間復(fù)雜度為 O(n) 的算法
  1、數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，也就是說它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)的和還要多。因此，我們可以考慮在遍歷數(shù)組的時候保存兩個值：一個是數(shù)組中的一個數(shù)字；另一個是次數(shù)。
  ２、當我們遍歷到下一個數(shù)字的時候，如果下一個數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加１；如果下一個數(shù)字和我們之前保存的數(shù)字不同，則次數(shù)減１；如果次數(shù)為０，那么我們需要保存下一個數(shù)字，并把次數(shù)設(shè)為１．
  ３、由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為１時對應(yīng)的而數(shù)字

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool checkVality(vector<int> numbers, int result){
        bool vality = true;
        int times = 0;
        for(int i=0; i < numbers.size(); i++){
            if(result == numbers[i]){
                times ++;
            }
        }

        if(times * 2 <= numbers.size()){
            vality = false;
        }
        return vality;
    }

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0){
            return 0;
        }

        int times = 1;
        int result = numbers[0];
        for(int i=1; i < numbers.size(); i++){
            if(times == 0){
                result = numbers[i];
                times = 1;
            }
            else if(result == numbers[i]){
                times ++;
            }
            else{
                times --;
            }
        }

        if(!checkVality(numbers, result)){
            result = 0;
        }
        return result;
    }
};

int main(){
    int a[10] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    int len = 9;
    vector<int> numbers;
    Solution ss;

    for(int i=0; i < len; i++){
        numbers.push_back(a[i]);
    }

    cout<<ss.MoreThanHalfNum_Solution(numbers)<<endl;
}

總結(jié)展望

• 有快排的思想在其中，題目很好，值得反復(fù)思考