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.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 题解： 此题是我找到的一个关于分治算法的题目，但是由于没有想到该如何运用分治算法求解，所以用了一个普通的方法。 我的思路是首先对数组进行排序，排序后相同数字都会被排在一起。然后就可以对排序后的数组一个个进行检查，运用一个整型数据count来记录每一种 数字的个数，如果前后有一样的数字就count++，如果count的大小超过了n/2，那么这个数字就是题目要求的最终结果。由于我作比较是用的count[i]和count[i+1]，所以在遍历时的范围是0到size-1，在majority element是最大的数字的情况下可能就会没办法识别到，所以最后的判断条件中还加入了i==size-1的情况。 代码： #include <algorithm> class Solution { public: int majorityElement(vector<int>& nums) { if (nums.size() == 1) return nums[0]; else { sort(nums.begin(), nums.end()); int count = 1; for (int i = 0; i < nums.size() - 1; i++) { if (nums[i] == nums[i + 1]) count++; else count = 1; if (count > nums.size() / 2 || i == nums.size() - 1) { return nums[i]; break; } } } } }; -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------另解：
由于此题是关于分治算法的题目，所以也搜索了此题运用分治算法的做法： class Solution { public: int majorityElement(vector<int>& nums) { return majority(nums, 0, nums.size() - 1); } private: int majority(vector<int>& nums, int left, int right) { if (left == right) return nums[left]; int mid = left + ((right - left) >> 1); int lm = majority(nums, left, mid); int rm = majority(nums, mid + 1, right); if (lm == rm) return lm; return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm; } }; 还有其他更多的解法：https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations/2