數組中出現次數超過一半的數字(C++劍指Offer詳解)

第一次見到這個題，感覺簡單到爆，不就是sort函數排個序，取中位數，遍歷一遍計個數不就OK了嗎？但是面試時，sort可能會讓你自己去實現，或者說，題目要求：不能修改輸入的數組呢？？？
第一種方法（基于Partition函數）
注意：此方法修改了輸入的數組

核心：出現次數超過一半的數字，排序后中位數肯定是這個數字

解題思路：通過Partition函數，隨機選出數組中的一個元素（我的代碼中默認是數組中第一個元素），并且通過快排的思想，小的元素移到隨機值前面，大的元素移到隨機值的后面，然后返回隨機值最后的位置。然后通過調用Partition函數，用返回的index值和中值判等，如果index>mid，說明中位數在左邊,end=mid-1,如果index<mid，說明中位數在右邊，start=mid+1,直到最后等于mid，然后numbers[mid]作為出現最多的數字，最后通過Check函數，判斷出現次數是否超過數組的一半

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        int length = numbers.size();
        if (length <= 0)//判空
            return 0;
        int start = 0;
        int end = length - 1;
        int index = Partition(numbers, start, end);//Partition函數隨機值在數組中的位置
        int mid = length >> 1;//統計學的中位數
        while (index != mid)//隨機值與中位數位置的判等
        {
            if (index>mid)
            {
                end = index - 1;
                index = Partition(numbers, start, end);
            }
            else if (index<mid)
            {
                start = index + 1;
                index = Partition(numbers, start, end);
            }
        }
        if (!Check(numbers, numbers[index]))//判斷次數是否超過一半
            return 0;
        return numbers[index];
    }
    int Partition(vector<int> num, int start, int end)
    {
        int index = start;
        int sum = num[start];//默認隨機值為首位，這里可以用“隨機函數”
        //從第二位開始
        for (int i = start + 1; i<end; ++i)
        {
            if (num[i]<sum)
            {
                ++index;
                swap(num[i], num[index]);
            }
        }
        swap(num[start], num[index]);//隨機值居中（左小右大）
        return index;
    }
    bool Check(vector<int> num, int result)
    {
        int count = 0;
        for (int i = 0; i<num.size(); ++i)
        {
            if (num[i] == result)
                ++count;
        }
        if (count * 2>num.size())
            return true;
        return false;
    }
};

第二種方法（計數法）
注意：此方法沒有修改輸入的數組

核心：出現次數超過一半的數字個數比其他所有數字個數至少多一

解題思路：從首位開始（result==numbers[0]），遇到相等的元素，count++，遇到不相等的元素，count--，當count==0時，result重新賦值為當前元素，重新給count賦值為1，直到數組遍歷完之后，返回result

疑惑？？？既然，判斷出來了，為什么還要調用Check函數，因為我們無法判斷result是否為出現次數最多的元素，就算是出現次數最多的元素，不知是否超過數組一半，例如：{5,5,5,5,5,3,3,3,4,4,4,4} {3,3,3,4,4,4,4,5,5,5,5,5}

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