力扣169. 多数元素

169. 多数元素

题目：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例一：

输入：nums = [3,2,3]
输出：3

思路一：使用字典，key是数组中的元素，value是出现的次数，value最大的key就是多数元素。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

思路二：排序法，因为众数超过数组长度的一半，所以中位数就是众数。

• 时间复杂度：O(nlog⁡n)
• 空间复杂度：O(log⁡n)

思路三：最优解，摩尔投票法 。

• 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
• 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

思路一：

public class Solution {
    public int MajorityElement(int[] nums) {
        if(nums.Length<1) return 0;
        int time = nums.Length/2;
        Dictionary<int,int> dic = new Dictionary<int,int>();
        for(int i = 0;i<nums.Length; i++){
            if(dic.ContainsKey(nums[i])){
                int value = dic[nums[i]];
                dic[nums[i]] = ++value;
            }else{
                dic.Add(nums[i],1);
            }
        }
        int max = 0;
        int maxKey = 0;
        foreach(KeyValuePair<int,int> pair in dic){
            if(pair.Value > nums.Length/2 && pair.Value > max){
                max = pair.Value;
                maxKey = pair.Key;
                break;
            }
        }
        return maxKey;
    }
}
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

思路二：

public class Solution {
    public int MajorityElement(int[] nums) {
            Array.Sort(nums);
            return nums[(nums.Length-1)/2];
    }
}
1
2
3
4
5
6

思路三：

public class Solution {
    public int MajorityElement(int[] nums) {
        //特殊情况判断
        if(nums.Length <= 2) return nums[0];
        int x = nums[0];
        int sum = 1;
        for(int i = 1;i<nums.Length;i++){
            //如果票数等于0，则刷新候选人
            if(sum == 0){
                x = nums[i];
                sum = 1;
            }else{
                //如果票上的信息是候选人，票数加1,否则票数减1
                if(nums[i] == x){
                    sum++;
                }else{
                    sum--;
                }
            }
            
        }
        return x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24