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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
这是到求众数的问题，有很多种解法，可参见网友烟雨林的博客，其中我感觉比较好的有两种，一种是用哈希表，这种方法需要O(n)的时间和空间，另一种是用一种叫摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间，比前一种方法更好。这种投票法先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。代码如下：
C++ 解法一：
class Solution { public: int majorityElement(vector<int>& nums) { int res = 0, cnt = 0; for (int num : nums) { if (cnt == 0) {res = num; ++cnt;} else (num == res) ? ++cnt : --cnt; } return res; } };
Java 解法一：
public class Solution { public int majorityElement(int[] nums) { int res = 0, cnt = 0; for (int num : nums) { if (cnt == 0) {res = num; ++cnt;} else if (num == res) ++cnt; else --cnt; } return res; } }
下面这种解法利用到了位操作Bit Manipulation来解，将中位数按位来建立，从0到31位，每次统计下数组中该位上0和1的个数，如果1多，那么我们将结果res中该位变为1，最后累加出来的res就是中位数了，相当赞的方法，这种思路尤其在这道题的延伸Majority Element II中有重要的应用，参见代码如下：
C++ 解法二：
class Solution { public: int majorityElement(vector<int>& nums) { int res = 0; for (int i = 0; i < 32; ++i) { int ones = 0, zeros = 0; for (int num : nums) { if ((num & (1 << i)) != 0) ++ones; else ++zeros; } if (ones > zeros) res |= (1 << i); } return res; } };
Java 解法二：
public class Solution { public int majorityElement(int[] nums) { int res = 0; for (int i = 0; i < 32; ++i) { int ones = 0, zeros = 0; for (int num : nums) { if ((num & (1 << i)) != 0) ++ones; else ++zeros; } if (ones > zeros) res |= (1 << i); } return res; } }
本文转自博客园Grandyang的博客，原文链接：求众数[LeetCode] Majority Element ，如需转载请自行联系原博主。