LeetCode 169. 求众数（Majority Element）

问题描述：

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

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

示例：

C语言实现：

我们很容易想到一种思路：对nums进行排序，排序完的数组nums[len(nums)/2]一定是众数。

这种方法简单直接，算法的复杂度是O(nlogn)。在此不提供代码了，大家可以自己写写。我们这里说一说另一种方法。

首先定义一个变量cur保存出现次数最多的那个数，我们假设数组第一个数是出现次数最多的，且将其计数为1。然后从数组的第二个数开始，如果它和cur相等，那么计数加1，如果不等计数减一，如果计数等于0的时候，说明到目前为止不等于cur的数和等于cur的数数量一样多。那么这个时候cur可能就不是众数，我们要从新开始，按照前面的方法，选择下一个数作为cur，并计数1。如此这般，最后cur保存的就是我们要找的众数。

代码如下：

注意第6行，不会发生数组越界的问题，因为按照题目，众数一定是存在的，所以这里不会越界。

第9行做了一个优化，针对于众数集中出现在数组左边的情况。

python语言的实现：

python推荐用第一种思路来解题，有两个好处：第一，代码简洁，只要一行；第二，sorted和len函数都是内置函数，是C语言实现的，通常效率要比纯python的高的多。

Java语言的实现：

Java的实现和C语言的实现相同。

代码如下：