面试题39：数组中出现次数超过一半的数字

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

常规方法1：

1. 若数组为空，返回0；
2. 若数组中只有一个数字，直接返回那个数字；
3. 对数组进行排序，vector<int>可直接用sort函数排序，然后设置两个前后位置i,j遍历找出出现次数大于数组一半的数字。找到后返回值即可。

   class Solution {
   public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.empty())
            return 0;
        //若元素只有一个，直接输出
        if (numbers.size() == 1)
            return numbers[0];
        sort(numbers.begin(), numbers.end());
        int i = 0, j = 1, count = 0, maxCount=0,number = 0;;
        while (i < numbers.size() && j < numbers.size())
        {
            if (numbers[i] != numbers[j])
            {
                count = 0;
                i = j;
                j++;
            }
            else
            {
                count++;
                number = numbers[j];
                if (2 * (count + 1) > numbers.size())
                {
                    return number;
                }
                j++;
            }        
        }
    return 0;
    }
   };

   </int>

补充：快速排序

#include<iostream>
using namespace std;

void print(int a[], int n)
{
    for (int j = 0; j < n; j++)
    {
        cout << a[j] << "  ";
    }
    cout << endl;
}
void quickSort(int a[], int low, int high)
{
    if (low < high)  //判断是否满足排序条件，递归的终止条件
    {
        int i = low, j = high;   //把待排序数组元素的第一个和最后一个下标分别赋值给i,j，使用i,j进行排序；
        int x = a[low];    //将待排序数组的第一个元素作为哨兵，将数组划分为大于哨兵以及小于哨兵的两部分                                   
        while (i < j)
        {
            while (i < j && a[j] >= x) j--;  //从最右侧元素开始，如果比哨兵大，那么它的位置就正确，然后判断前一个元素，直到不满足条件
            if (i < j) a[i++] = a[j];   //把不满足位次条件的那个元素值赋值给第一个元素，（也即是哨兵元素，此时哨兵已经保存在x中，不会丢失）并把i的加1
            while (i < j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小，比其小，那么它所处的位置就正确，然后判断后一个，直到不满足条件
            if (i < j) a[j--] = a[i];  //把不满足位次条件的那个元素值赋值给下标为j的元素，（下标为j的元素已经保存到前面，不会丢失）并把j的加1
        }
        a[i] = x;   //完成一次排序，把哨兵赋值到下标为i的位置，即前面的都比它小，后面的都比它大
        quickSort(a, low, i - 1);  //递归进行哨兵前后两部分元素排序 ， low,high的值不发生变化，i处于中间
        quickSort(a, i + 1, high);
    }
}

int main()
{
    int a[10] = { 8,1,9,7,2,4,5,6,10,3 };
    cout << "初始序列：";
    print(a, 10);
    quickSort(a, 0, 9);
    cout << "排序结果：";
    print(a, 10);
    system("pause");
}

方法2：借助快排的思想

class Solution {
public:
/*
思路：若某个数字出现的次数超过了数组长度的一半，则排序之后位于中间的数一定就是要找的那个数，相当于中位数，所以我们可以求出位于数组的中位数，类似于快排。
先随机找一个数，使得比这个数小的都在其左边，比这个数大的都在其右边。如果选中的这个数的下标刚好等于n/2，那么这个数字就是我们要找的中位数。
具体实现可以通过递归来做。
随机选定一个数，一次快排之后确定这个数的位置，若小于n/2,则中位数在他的右边；若大于n/2，则中位数在他的左边。直到找到下标为n/2的数。
*/
    //一次快排
    int quickSort(vector<int>& numbers, int begin, int end)
    {
        int i = begin, j = end, baseVal = numbers[begin];
        while (i<j)
        {
            while (i<j && numbers[j]>=baseVal)
            {
                j--;
            }
            if (i < j)
            {
                numbers[i++] = numbers[j];
            }
            while (i<j&&numbers[i]<=baseVal)
            {
                i++;
            }
            if (i < j)
            {
                numbers[j--] = numbers[i];
            }

        }
        //注意这里一定要给最终找到的位置赋值啊，返回一次快排确定的位置
        numbers[i] = baseVal;
        return i;
    }
    //number为已经检测到的中位数，遍历整个数组，找出中位数的个数，若大于数组的一个，返回true
    bool checkMoreThanHalf(vector<int>& numbers, int number)
    {
        int count = 0;
        for (int i = 0; i < numbers.size(); i++)
        {
            if (numbers[i] == number)
            {
                count++;
            }
        }

        if (count*2 > numbers.size())
        {
            return true;
        }
        return false;
    }


    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
        int len=numbers.size();
        int middle = len >> 1;
        int start=0, end=len-1;
        int pos=quickSort(numbers, 0, end);
        //找到中位数
        while (pos!=middle)
        {
            //若pos大于中间位置，则中位数位于pos前面
            if (pos > middle)
            {
                end = pos - 1;
                pos = quickSort(numbers, start, end);
            }
            //若pos小于中间位置，则中位数位于pos后面
            else
            {
                start = pos + 1;
                pos = quickSort(numbers, start, end);
            }
        }
        int result = numbers[pos];
        if (checkMoreThanHalf(numbers, result))
            return result;
        return 0;
    }
};

方法3：根据数组特点，时间复杂度O(N)

class Solution {
public:
    /*
    思路：若数组中有一个次数大于数组一半的数字，则它出现的次数大于其他所有数字次数的总和。
    所以我们考虑遍历数组的时候保存两个值，一个是数组中的数字，另一个是次数。
    当我们遍历的下一个数字若与之前保存的数字相同，计数加1，若不同，计数减1。
    当计数变为0时，保存下一个数字并设置次数为1，由于我们要找的数字出现的次数比其他所有数字出现次数之和还要多，
    所以最后找的数字肯定是最后一次把数字设置成为1时对应的数字。
    */
    bool checkMoreThanHalf(vector<int>& numbers, int number)
    {
        int count = 0;
        for (int i = 0; i < numbers.size(); i++)
        {
            if (numbers[i] == number)
            {
                count++;
            }
            if (count * 2 > numbers.size())
            {
                return true;
            }
        }
        return false;
    }

    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
        if (numbers.empty())
            return 0;
        int count = 1, number = numbers[0];
        //遍历得到最后一个次数设为1的数字
        for (int i = 1; i < numbers.size(); i++)
        {
            if (numbers[i] == number)
                count++;
            else
                count--;
            if (count == 0)
            {
                number = numbers[i];
                count = 1;
            }
        }

        if (checkMoreThanHalf(numbers, number))
            return number;
        else
            return 0;
    }

};

方法4：哈希法：利用map函数。先遍历一遍数组，在map中存储每个元素出现的次数，然后遍历一次数组，找出众数

class Solution {
public:
   //哈希法：利用map函数。先遍历一遍数组，在map中存储每个元素出现的次数，然后遍历一次数组，找出众数
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        map<int, int> mapNumbers;
        for (int i = 0; i < numbers.size(); i++)
        {
            mapNumbers[numbers[i]]++;
        }
        for (int i = 0; i < mapNumbers.size(); i++)
        {
            if (mapNumbers[i] * 2 > numbers.size())
                return i;
        }
        return 0;
    }
};