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. Difficulty：Easy
这道题的要求是找出输入数组中出现次数最多的元素。 按照Divide and Conquer的思想，可以将数组对半分，找出每一半出现次数最多的元素，将两半出现的次数进行比较，整合得到完整的数组中出现次数最多的元素。设置mid变量，进行多次递归，整合得到最终结果。 怎么数出元素出现的次数呢？ algorithm头文件中定义了一个count函数，其功能类似于find。这个函数使用一对迭代器和一个值做参数，返回这个值出现次数的统计结果。形式如下：
count(ivec.begin() , ivec.end() , searchValue)本题完整的代码如下：
class Solution {public: int findMajor(vector<int>& nums, int left, int right){ if(left == right) return nums[left]; int mid = left + (right - left) / 2; //对半分割数组 int ll = findMajor(nums, left, mid); int rr = findMajor(nums, mid + 1, right); if(ll == rr) return ll; if(count(nums.begin() + left, nums.begin() + right + 1, ll) > count(nums.begin() + left, nums.begin() + right + 1, rr)) //比较两半中哪个元素出现的次数最多 return ll; else return rr; } int majorityElement(vector<int>& nums) { return findMajor(nums, 0, nums.size() - 1); }};新闻热点
疑难解答
