题解 | #数组中出现次数超过一半的数字#

题目：数组中出现字数超过一半的数字

描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000

示例1：输入：[1,2,3,2,2,2,5,4,2]返回值：2

解法一思路分析：看到题目以后，首先应该要知道用暴力法解决问题，因为在题目中规定了次数，所以我们应该在程序中设定一个count的int类型，表示次数的多少，其次设定一个i和j指针，还是使用定i变j法，逐一进行判断，最后的结果为当count的值超过总字符数的一半时，即返回i位置的值即可。

举例分析：[1,2,3,2,2,2,5,4,2]

具体C语言代码为：

/**
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    int count;//次数
    int b = 0;
    for(int i = 0; i < numbersLen; i++){
        int a = numbers[i];//将第一个字符赋予a
        count = 0;
        for(int j = 0; j < numbersLen; j++){
            if(a == numbers[j])//进行判断
                count++;
        }
        if(count > (numbersLen / 2)){
            b = a;
            break;
        }
    }
    return b;
}

该算法的时间复杂度为O(N)。

解法二思路分析：将数组排序后，中间值肯定是要查找的值，直接将中间值返回即可。该算法通俗易懂，便不进行具体例子分析。

C++语言代码如下所示：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());//排序        
        int len = numbers.size();
        return numbers[len/2];
    }
};

该算法的时间复杂度为O(1)。