169. 多数元素

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个大小为\(n\)的数组，找到其中的多数元素。 多数元素是指在数组中出现次数大于 \(⌊ n/2 ⌋\)​ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1: >输入:[3,2,3] >输出: 3

示例 2: >输入:[2,2,1,1,1,2,2] >输出: 2

进阶：

  • 尝试设计时间复杂度为 \(O(n)\)、空间复杂度为 \(O(1)\) 的算法解决此问题。

我的代码 1: 排序

\(T(N) = O(NlogN)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
class MySolution169_1 
{
    public int majorityElement(int[] nums) 
    {
    	Arrays.sort(nums);
    	if (nums.length%2==0)
    		return nums[nums.length/2-1];
    	else return nums[nums.length/2];
    	
    	return nums[nums.length/2];
    }
}

我的代码 2: 哈希表

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MySolution169_2
{
    public int majorityElement(int[] nums) 
    {
    	HashMap<Integer, Integer> map = new HashMap();
    	
    	for (int num:nums)
    	{
    		if (!map.containsKey(num))
    			map.put(num, 1);
    		else map.put(num, map.get(num)+1);
    		
    		if (map.get(num)>nums.length/2)
    			return num;
    	}
    	
    	return -1;
    }
}

方法一: 分治法

\(T(N) = O(NlogN)\), \(S(N) = O(logN)\)

如果元素num是数组nums的众数， 那么将nums分为两部分时，num必定至少是其中某一部分的众数。

用反证法对这一结论进行证明： 设l为左半部分的长度，r是右半部分的长度， 假设num既不是左半部分的众数，也不是右半部分的众数， 那么num的出现次数将小于(l/2+r/2)次； 又由于(l/2+r/2)≤(l+r)/2，说明num也不是数组nums的众数，因此出现了矛盾。 可见结论是正确的。

因此，可以将数组分为左右两部分， 分别求出左半部分的众数num1和右半部分的众数num2， 再在num1和num2之间选出正确的那个众数。

通过递归的分治算法来求解。 当所有子问题的长度都是1时，这唯一一个数显然就是众数，直接返回； 当回溯后区间长度大于1时， 若左右子区间的众数相同，则合并后区间的众数显然就是这个值； 若左右子区间的众数不同，则需要比较两个众数在合并后整个区间内的出现次数来决定取谁。

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution169
{
    public int majorityElement(int[] nums) 
	{
    	return split(nums,0,nums.length-1);
    }
    
    public int findVal (int []nums, int head, int tail, int val1, int val2)
    {
    	int count1=0, count2=0;
    	
    	for (int i=head; i<=tail; i++)
    	{
    		if (val1==nums[i]) count1++;
    		else if (val2==nums[i]) count2++;
    	}
    	
    	return count1>count2?val1:val2;
    }
    
    public int split(int []nums, int head, int tail)
    {
    	if (head==tail) return nums[head];
    	
    	int mid = head+(tail-head)/2;
    	int leftVal = split(nums, head, mid);
    	int rightVal = split(nums, mid+1, tail);
    	
    	if (leftVal==rightVal) return leftVal;
    	
    	else return findVal(nums, head, tail, leftVal, rightVal);
    }
}

时空复杂度

  • 时间复杂度\(O(NlogN)\): 函数split()会求解两个长度为\(\frac {n}{2}\)的子问题，并做两次长度为\(n\)的线性扫描。因此分治算法的时间复杂度可以表示为\(2T(\frac {n}{2})+2n\). 根据主定理，本题的时间复杂度为\[T(n)=\Theta(n^{log_ba}logn)=\Theta(n^{log_22}logn)=\Theta(nlogn)\]
  • 空间复杂度\(O(1)\).

方法二：摩尔投票法Boyer-Moore

\(T(N) = O(N)\), \(S(N) = O(1)\)

如果我们把众数记为+1，其他数记为-1，将它们全部加起来，和显然大于0。

维护一个候选众数candidate和其出现次数count。初始candidate任意，count为0. 遍历nums中的元素。在判断nums[i]之前，若count为0则将nums设置为candidate。 若nums[i]与candidate相等，则count加1； 若nums[i]与candidate不等，则count减1； 遍历结束后的candidate就是众数。

摩尔投票算法的正确性较难证明，可以通过一个例子来理解. nums为数组，candidate为候选众数，count为候选众数的出现次数(非负)， value为目前为止真正的众数比非众数多出现的次数 (如果nums[i]是真正的众数则加1，否则减1)。 nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7 count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4 value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4

可以发现 当candidate就是众数时count和value相等，否则它们互为相反数。 这是因为： 我们将候选众数candidate保持不变的连续的遍历称为「一段」。 在同一段中，count的值根据candidate是否等于nums[i]进行加减。 那么如果candidate就是众数，则在这一段中，count和value的变化是同步的； 如果candidate不是众数，则在这一段中，count和value的变化是相反的。

由于value的值与真正的众数绑定， 并且它表示「目前为止真正的众数比非众数多出现的次数」， 因此在遍历的最后，value的值是正数。

即在最后一次遍历后，count非负、value为正数， 因此它们不会互为相反数，只可能相等。 可见在最后的「一段」中，count和value的变化是同步的， 即candidate绑定的候选众数就是真正的众数。

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution169 
{
    public int majorityElement(int[] nums) 
	{
		int candidate = 0; int count = 0;
    	
    	for (int num:nums)
    	{
    		if (count==0) candidate  = num;
    		
    		if (candidate==num) count+=1;
    		else count-=1;
    	}
    	
    	return candidate;
    }
    
}