剑指offer:数组中出现次数超过一半的数字

题目描述

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

方法1

利用快排的partion

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {

        int len = numbers.size();

        if (len == 0){
            return 0;
        }

        int index = partition(numbers, 0, len - 1);

        int mid = (len - 1) >> 1;

        int left = 0, right = len - 1;

        while (index != mid){
            if (index < mid){
                left = index + 1;
                index = partition(numbers, left, right);
            }
            else{
                right = index - 1;
                index = partition(numbers, left, right);
            }
        }

        int cnt = 0;
        for (int num : numbers){
            if (num == numbers[mid]){
                cnt++;
            }
        }

        //不能用mid+1来判断，因为2*（mid+1）不一定等于len
        return cnt*2 > len ? numbers[mid] : 0;
    }

private:
    int partition(vector<int> &numbers, int left, int right){

        int i = left, j = right;
        int pivot = numbers[i];

        while (i < j){
            while (i < j && numbers[j] > pivot) j--;
            if (i < j){
                numbers[i++] = numbers[j];
            }

            while (i < j && numbers[i] <= pivot) i++;
            if (i < j){
                numbers[j--] = numbers[i];
            }

        }
        numbers[i] = pivot;

        return i;
    }

};

方法二

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {

        int len = numbers.size();

        if (len == 0){
            return 0;
        }

        int num = numbers[0];
        int cnt = 1;

        for (int i = 1; i < len; i++){

            if (cnt == 0){
                num = numbers[i];
                cnt = 1;
                continue;
            }

            if (numbers[i] == num){
                cnt++;
            }
            else{
                cnt--;
            }
        }

        int times = 0;
        for (int n : numbers){
            if (n == num){
                times++;
            }
        }

        return 2 * times > len ? num : 0;

    }
};