leetcode算法题-169.多数元素

发表于 | 分类于 | 阅读次数: |

题目

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

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

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer count = map.getOrDefault(num, 0);
            count++;
            map.put(num, count);
        }
        Integer max = 0;
        Integer result = 0;
        for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
            if(integerIntegerEntry.getValue() > max){
                result = integerIntegerEntry.getKey();
                max = integerIntegerEntry.getValue();
            }
        }
        return result;
    }
}

利用map统计出现次数，在遍历map找到出现最多的key。

执行用时：16 ms, 在所有 Java 提交中击败了26.21%的用户
内存消耗：44 MB, 在所有 Java 提交中击败了20.36%的用户

显然存在更好的算法。

题解版-Boyer-Moore 投票算法

题解中还有排序方法。综合看来下投票法最妙！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

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

思路：如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来，显然和大于 0。
开始看到投票法时还不理解通过断点调试才慢慢理解。