169. Majority Element--寻找数组中出现次数超过一半的数据，229. Majority Element II--注意最后的检测

本文主要是介绍169. Majority Element--寻找数组中出现次数超过一半的数据，229. Majority Element II--注意最后的检测，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题、169. Majority Element-
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.
方法一、由于出现一半的数字，则即寻找第middle大的数字，可以基于快速排序的partition的思想，然后找出第Middle大的数字，代码此处省略；
方法二、hash的方法；
方法三、基于出现次数超过一半的数据的特征，代码如下：

int majorityElement(vector<int>& nums) {if(nums.size()<=0)return -1;int count = 1;int result = nums[0];for(int i = 1; i < nums.size(); i++){if(count == 0){result = nums[i];count = 1;}else if(nums[i] == result){count++;}else{count--;}}return result;}

第二题、229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

/*求众数的问题观察可知，数组中至多可能会有2个出现次数超过 ⌊ n/3 ⌋ 的众数;记变量num1, num2为候选众数； cnum1, cnum2为它们对应的出现次数遍历数组，记当前数字为num若num与num1或num2相同，则将其对应的出现次数加1否则，若cnum1或cnum2为0，则将其置为1，对应的候选众数置为num否则，将cnum1与cnum2分别减1最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。*/vector<int> majorityElement(vector<int>& nums) {int len = nums.size();if(len <= 0){return (vector<int> ());}int num1 = 0,num2 = 1;int cnum1 = 0,cnum2 = 0;for(int i = 0; i < len; i++){if(nums[i] == num1){cnum1++;}else if(nums[i] == num2){cnum2++;}else if(cnum1 == 0){num1 = nums[i];cnum1 = 1;}else if(cnum2 == 0){num2 = nums[i];cnum2 = 1;}else{cnum1--;cnum2--;}}cnum1 = 0;cnum2 = 0;for(int i = 0; i < len; i++){if(nums[i] == num1){cnum1++;}else if(nums[i] == num2){cnum2++;}}vector<int> result;if(cnum1 > len / 3){result.push_back(num1);}if(cnum2 > len / 3){result.push_back(num2);}return result;}