数组中出现次数超过一半的数字(C++剑指Offer详解)

第一次见到这个题，感觉简单到爆，不就是sort函数排个序，取中位数，遍历一遍计个数不就OK了吗？但是面试时，sort可能会让你自己去实现，或者说，题目要求：不能修改输入的数组呢？？？
第一种方法（基于Partition函数）
注意：此方法修改了输入的数组

创新互联建站坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、网站制作、成都外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的泗水网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

核心：出现次数超过一半的数字，排序后中位数肯定是这个数字

解题思路：通过Partition函数，随机选出数组中的一个元素（我的代码中默认是数组中第一个元素），并且通过快排的思想，小的元素移到随机值前面，大的元素移到随机值的后面，然后返回随机值最后的位置。然后通过调用Partition函数，用返回的index值和中值判等，如果index>mid，说明中位数在左边,end=mid-1,如果index

class Solution {
public:
    int MoreThanHalfNum_Solution(vector 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 num, int start, int end)
    {
        int index = start;
        int sum = num[start];//默认随机值为首位，这里可以用“随机函数”
        //从第二位开始
        for (int i = start + 1; i num, int result)
    {
        int count = 0;
        for (int i = 0; inum.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 numbers) {
        if(numbers.size()<=0)
            return 0;
        int result=numbers[0];
        int i=1;
        int count=1;
        for(;i num,int result)
    {
        int count=0;
        for(int i=0;inum.size())
            return true;
        return false;
    }

文章标题：数组中出现次数超过一半的数字(C++剑指Offer详解)
网站URL：http://6mz.cn/article/pgjijh.html