題目描述

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半姨蟋，請(qǐng)找出這個(gè)數(shù)字闷沥。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}描焰。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半特恬，因此輸出2执俩。如果不存在則輸出0。

第一想法

• 排序癌刽，遍歷役首，記錄最大的i

寫代碼發(fā)現(xiàn)是輸出該數(shù)字,不用輸出長度...原來第一版寫錯(cuò)了
第一版代碼↓

• 先排序,記錄下重復(fù)次數(shù)的數(shù)字和數(shù).如果遇到重復(fù)次數(shù)更多的,則替換數(shù)字,數(shù)清零.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers);
        int num = 0, tmp = 0,numm;
        if(numbers.size() == 1)
            return numbers[0];
        if(numbers.size() < 2){
            return 0;
        }
        for(int i = 1; i < numbers.size(); i++){
            tmp++;
            if(numbers[i - 1] != numbers[i]){
                if(num < tmp){
                    num = tmp;
                    numm = numbers[i - 1];
                }
                tmp = 0;
            }
            else{
                if(i == numbers.size() - 1){
                    tmp++;
                    if(tmp > num)
                        num = tmp;
                }
            }
        }
        if(num > numbers.size()/2)
            return numm;
        else
            return 0;
    }
    
    //冒泡排序 
    void sort(vector<int> &h)
    {
        if(h.size() == 0) return;
        if(h.size() <= 1) return;
        for(int i = 0;i < h.size() - 1;++i)
            for(int j = 0;j < h.size() - 1 - i;++j)
                if(h[j] > h[j + 1]){
                    h[j] = h[j] + h[j + 1];
                    h[j + 1] = h[j] - h[j + 1];
                    h[j] = h[j] - h[j + 1];
                }
        return;
    }
};

我再改改

• 先排序,找到中間的數(shù)字,看數(shù)字的cnt是否占一半多.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0) return 0;
        sort(numbers);
        int num = numbers[numbers.size()/2];
        int count = 0;
        for(int i = 0;i < numbers.size();++i){
            if(numbers[i] == num)
                count++;
        }
        if(count > numbers.size()/2)
            return num;
        else
            return 0;
    }
    
    void sort(vector<int> &h)
    {
        if(h.size() == 0) return;
        if(h.size() <= 1) return;
        for(int i = 0;i < h.size() - 1;++i)
            for(int j = 0;j < h.size() - 1 - i;++j)
                if(h[j] > h[j + 1]){
                    h[j] = h[j] + h[j + 1];
                    h[j + 1] = h[j] - h[j + 1];
                    h[j] = h[j] - h[j + 1];
                }
        return;
    }
};

我采用的是冒泡排序的方法,用歸并排序復(fù)雜度還要小一些O(N^2)+O(N);

將排序法替換掉,使用stack的思路,遇見不同的就出棧,然后進(jìn)后面那個(gè)不同的,遇見相同的就入棧.最后棧底里剩的就是count最大的數(shù).當(dāng)然這種思路可以直接轉(zhuǎn)化為 int 數(shù)字和 int 數(shù)量來保存.用棧就是好表達(dá)一點(diǎn).

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