本文共 1717 字，大约阅读时间需要 5 分钟。

题目大意：

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3]输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]输出: 2

解法1：

from collections import Counterclass Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        tmp = Counter(nums).most_common()  # 利用Counter统计出现次数        for i in range(len(tmp)):            if tmp[i][1] > len(nums) / 2:  # 谁满足大于n/2就返回谁，题目已经说非空切一定存在众数，所以不做其他情况的讨论了。                return tmp[i][0]

解法2：

众数是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。那么问题就很容易了，我们可以先将nums排序，然后返回中间元素的值即可（众数的个数大于一半，排好序的nums中间元素一定是众数）

class Solution:    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        nums.sort()        return nums[len(nums)//2]

在pyhon3中/ 是真除法： 3/2=1.5

地板除是//，是取整数位： 3//2=1

% 表示求余数： 5%2=1

以下是Java版本：

题目大意：给定一个数组，找这个数组中的主元素，主元素是元素出现次数大于⌊ n/2 ⌋的元素。 假设给定的数组非空，主元素都存在。 

解题思路： 用一个标记cnt记录某个元素出现的次数，如果后面的元素和它相同就加一，有一个元素和他不相同就减一，当cnt小于等于0时重新记录新的元素。

分析如下：

从头到尾扫描一遍数组，记录当前的majority element的count。

1.	public class Solution {  2.	    public int majorityElement(int[] num) {  3.	        if(num.length < 3) return num[0];  4.	        int majority = num[0];  // 用于记录主元素，假设第一个是主元素5.	        int count = 1;  // 用于抵消数的个数6.	        //1,1,1,1,2,1,3,1,2,2,2,2,2,2,  7.	        for (int i = 1; i < num.length; ++i) {  // 从第二个元素开始到最后一个元素8.	            if (count == 0) {  // 如果两个数相同就不能抵消9.	                majority = num[i];  // 记录最后不可以抵消的数10.	                ++count;  11.	            } else if (num[i] == majority)  {  12.	                ++count;  13.	            } else {  14.	                --count;  15.	            }  16.	        }  17.	        return majority;  18.	    }  19.	}

转载地址：http://xsuvi.baihongyu.com/