题目
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例1：
输入: [3,2,3]
输出: 3
示例2：
输入: [2,2,1,1,1,2,2]
输出: 2
方法一: 暴力破解
算法
最简单最直接的方法是统计每个数出现的次数，如果它出现的次数 大于 , 则这个数就为这个数组的众数。因此实现此算法，需要两个嵌套的 for 循环，外层循环遍历数组来确定当前值，内层循环同样遍历数组，它则用来统计当前值出现的次数。
public class LeetCode_169 {
public int majorityElement(int[] nums) {
/**
* O(n^2)
* Time Limit Exceeded
*/
int max = 0;
for (int i = 0; i < nums.length; ++i) {
int count = 0;
for(int j = 0; j < nums.length; ++j) {
if (nums[i] == nums[j])
++count;
}
max = Math.max(max, count);
if (max > nums.length / 2)
return nums[i];
}
return -1;
}
}
复杂度分析
-
时间复杂度：
由于该方法包含两个嵌套的 for 循环，每个循环迭代n次，因此该算法的时间复杂度为
空间复杂度：
方法二： HashMap
算法
在统计元素出现次数的时候， 我们可以使用一个 HashMap 来保存当前已出现的元素出现的次数，这样可以避免重复的统计，从而在一个 for 循环里完成任务。
/**
* @author Maosong Ran
* @date 2018/10/06
* @email maosongran@gmail.com
*/
public class LeetCode_169 {
public int majorityElement(int[] nums) {
/**
* O(n) O(n)
*/
HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int i=0; i < nums.length; ++i) {
Integer num = count.get(nums[i]);
if (num == null)
num = 1;
else
++num;
if (num > nums.length / 2)
return nums[i];
count.put(nums[i], num);
}
return nums[0];
}
}
复杂度分析
-
时间复杂度：
由于我们只需要遍历一次数组，即可完成统计任务，因此，时间复杂度为
空间复杂度：
由于数组总存在众数，而众数的条件是其出现次数大于,因此最坏情况，HashMap包含
个元素，最好情况包含 1 个元素，因此空间复杂度为O(n)
方法三： 排序
由于众数的是其出现次数大于 的值，因此无论该值的大小是多少，该值总会出现在中心位置：对于数组长度为偶数时，为最中间两个数，为基数时，为最中间一个数。
上图中，数组下面的线表示当众数出现在排序数组的最左侧，数组上面的线表示当总数出现在排序数组的最右侧时，测试是众数出现的两个极端情况，其余情况在这两种情况之间，因此总数总是出现在排序数组的最中心位置。
public class LeetCode_169 {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
复杂度分析
-
时间复杂度：
在Java和Python中，数组排序的时间复杂度为
-
空间复杂度：
或
如果允许在原地进行排序时，我们不需要额外的空间，因此，空间复杂度为
,如果不允许，则需要额外的等大的数组来存放该有序数组，因此空间复杂度为
方法三： 分治法
算法
分治法是算法中经常遇到的一种求解问题的方法，它将大问题小化，复杂问题简单化，因此可以很容易得出问题的解。
在本题中，我们将数组递归地从中间将大数组分成左右两个小数组，然后求左右两个小数组的的众数，如果这两个众数相等，则这个数也是大数组的众数，如果两个数不相等，则这二者之一必有一个是大数组的众数，为什么呢？
若假设这两个数之一不是大数组的众数，由于他们是小数组的众数，因此，他们出现次数各占小数组的一半以上，因此这两个数在大数组中的出现次数必大于 ,因此剩下位置的值即便是相同，他们出现的次数也不大于
public class LeetCode_169 {
public int majorityElement(int[] nums) {
return divideAndConquer(nums, 0, nums.length-1);
}
private int divideAndConquer(int[] nums, int left, int right) {
if (left == right)
return nums[left];
else {
int mid = (left + right)/2;
int leftMajority = divideAndConquer(nums, left, mid);
int rightMajority = divideAndConquer(nums, mid + 1, right);
// System.out.println(leftMajority + "->" + rightMajority);
if (leftMajority == rightMajority)
return leftMajority;
int leftCount = 0;
int rightCount = 0;
for(int i=left; i <= right; ++i) {
if (nums[i] == leftMajority)
++leftCount;
else if (nums[i] == rightMajority) {
++rightCount;
}
}
// System.out.println(leftMajority + ":" + leftCount + ", " + rightMajority + ": " + rightCount);
return leftCount > rightCount ? leftMajority : rightMajority;
}
}
}
复杂度分析
时间复杂度：
空间复杂度：
方法五： 摩尔投票法
算法
大致思路，首先有一个统计当前投票数的变量 count， 当 count == 0 时，我们以当前变量作为候选众数，然后从当前变量位置开始，若值等于候选众数的值，则count加1，若不相等，则减一，依次遍历玩数组，当遍历完数组，若 count == 0，则该数组不存在众数，不等于0时，此时的候选众数即位真正的众数。
原理： 由于众数票数大于 ,因此即便它的票数减去其他所有的票数，它的票数也大于零。
public class LeetCode_169 {
public int majorityElement(int[] nums) {
int count = 0;
Integer candiate = null;
for(int num : nums) {
if (count == 0) {
candiate = num;
}
count += (candiate == num) ? 1 : -1;
}
return candiate;
}
}
复杂度分析
时间复杂度：
空间复杂度：
