剑指 Offer 39. 数组中出现次数超过一半的数字

题目：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例1：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

思路一：

要找出在数组中出现次数超过数组长度的一半，可以利用算法库中的sort函数将数组排序后中间的数据就是要找的数据；

再对数组进行遍历统计中间数据出现次数是否超过数组长度一半。

代码如下：

#include <vector>
class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {sort(numbers.begin(),numbers.end());//先排序int num = numbers[numbers.size()/2];//得到中间数据int count = 0;for(int i = 0; i < numbers.size(); i++) //对数组进行遍历{if(numbers[i] == num){count++;//统计num出现次数}}if(count > numbers.size()/2)//确认是否超过一半return num;return 0;}
};

时间复杂度：O(NlgN)，sort函数时间复杂度是O(N*lgN)，遍历时间复杂度为O(N)。

空间复杂度：O(1)

思路二：

消除不相等的，最后剩下的就是出现次数最多的。

众数：一组数中出现次数最多的那个数；本题中出现次数超过一半的数字就是众数。
如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。如示例中[1, 2, 3, 2, 2, 2, 5, 4, 2]，每次消去两个不相同的数字，那么最后剩下的数字2就是出现次数超过一半的。

代码如下：

class Solution {
public:int majorityElement(vector<int>& nums) {if(nums.empty())return 0;//遍历每个元素，并记录次数;若与前一个元素相同，则次数加1，否则次数减1int result = nums[0];int times = 1;//遍历数组，当数组中与result元素相同则++times，否则--timesfor(int i = 1; i < nums.size(); i++){if(times != 0){if(nums[i] == result){++times;}else{--times;}}else{result = nums[i];times = 1;}}   times = 0;for(int i = 0; i < nums.size(); i++){if(nums[i] == result) ++times;}//检查是否超过一半，如果超过则直接返回result，不超过则返回0return (times > nums.size() / 2) ? result : 0;}
};