题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

第一想法

• 排序，遍历，记录最大的i

写代码发现是输出该数字,不用输出长度...原来第一版写错了
第一版代码↓

• 先排序,记录下重复次数的数字和数.如果遇到重复次数更多的,则替换数字,数清零.

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;
    }
};

我再改改

• 先排序,找到中间的数字,看数字的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;
    }
};

我采用的是冒泡排序的方法,用归并排序复杂度还要小一些O(N^2)+O(N);

将排序法替换掉,使用stack的思路,遇见不同的就出栈,然后进后面那个不同的,遇见相同的就入栈.最后栈底里剩的就是count最大的数.当然这种思路可以直接转化为 int 数字和 int 数量来保存.用栈就是好表达一点.

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;
    }
};