169. 多数元素(简单)

Posted on In Views:

1，问题描述

169. 多数元素

难度：简单

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

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

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -109 <= nums[i] <= 10^9

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

2，初步思考

​ 题目是一道简单题，但是我觉得他在有算法复杂度要求的情况下，并不简单

3，代码处理

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package questions;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _169多数元素 {


    // 暴力求解，计数多余一半即可
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public int majorityElement_brute(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int half = n / 2;
        for (int num : nums) {
            int cnt = map.getOrDefault(num, 0) + 1;
            if(cnt > half){
                return num;
            }else {
                map.put(num, cnt);
            }
        }
        return -1;
    }

    // 排序法，排序完成下标为n/2的数就是答案
    // 时间复杂度：O(nlogn)，空间复杂度：O(1)
    public int majorityElement_sort(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    // 随机化，随机化取数，如果取到的数和之前的数相同，则计数加1，如果计数大于n/2，则返回当前数，否则继续随机取数
    // 时间复杂度：O(n)，空间复杂度：O(1)
    public int majorityElement_random(int[] nums) {
        int n = nums.length;
        int half = n / 2,cnt=0,res = nums[0],next=nums[0],idx=0;
        boolean flag = true;
        while (cnt<=half){
            cnt = 0;
            res = next;
            flag = true;
            for (int i = 0; i < n; i++) {
                if(nums[i]==res){
                    cnt++;
                    if(cnt>half) return res;
                }else {
                    if(flag&&idx<i){
                        idx = i;
                        next = nums[i];
                        flag = false;
                    }
                }
            }
        }
        return res;
    }

    // 分治
    public int majorityElement_divide(int[] nums) {
        int n = nums.length;
        int res = nums[0];
        majorityElement_divide_conquer(nums, 0, n/2);
        majorityElement_divide_conquer(nums, n/2, n);
        for (Map.Entry<Integer, Integer> integerIntegerEntry : mapMode.entrySet()) {
            if(integerIntegerEntry.getValue()>n/2){
                return integerIntegerEntry.getKey();
            }
        }
        return -1;
    }
    Map<Integer,Integer> mapMode = new HashMap<>();
    public int majorityElement_divide_conquer(int[] nums, int left, int right) {
        if(left==right) return nums[left];
        int mid = (right-left) / 2+left;// 防止int 溢出
        int newLeft = majorityElement_divide_conquer(nums, left, mid);
        int newRight = majorityElement_divide_conquer(nums, mid + 1, right);
        if (newLeft == newRight) {
            return left;
        }
        int leftCount = countInRange(nums, newLeft, left, right);
        int rightCount = countInRange(nums, newRight, left, right);
        return leftCount > rightCount ? left : right;
    }
    // 计算num的个数
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    // Boyer-Moore 投票算法
    /**
     * “同归于尽消杀法” ：
     * 由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。
     * 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
     * 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count++；
     * 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力count --。（即使双方都死光，这块高地的旗帜 winner 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）
     * 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。
     */
    public int majorityElement_boyer_moore(int[] nums) {
        int cnt = 0, res = 0;
        for (int num : nums) {
            if(cnt==0){
                res = num;
                cnt++;
            }else {
                if(res==num){
                    cnt++;
                }else {
                    cnt--;
                }
            }
        }
        return res;
    }

}