问题

数组中占比超过一半的元素称之为主要元素。给你一个整数数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为O(N)、空间复杂度为O(1)的解决方案

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

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

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

哈希表

  1. class Solution(){
  2. public int majorityElement(int[] nums){
  3. int n = nums.length;
  4. Map<Integer, Integer> map = new HashMap<>();
  5. for(int x : nums){
  6. map.put(x, map.getOrDefault(x, 0) + 1);
  7. if(map.get(x) > n / 2) return x
  8. }
  9. return -1;
  10. }
  11. }
  • 时间复杂度:面试题17.10.主要元素 - 图1
  • 空间复杂度:面试题17.10.主要元素 - 图2

摩尔投票

image.png

  1. class Solution {
  2. public int majorityElement(int[] nums) {
  3. int candidate = -1;
  4. int count = 0;
  5. for (int num : nums) {
  6. if (count == 0) {
  7. candidate = num;
  8. }
  9. if (num == candidate) {
  10. count++;
  11. } else {
  12. count--;
  13. }
  14. }
  15. count = 0;
  16. int length = nums.length;
  17. for (int num : nums) {
  18. if (num == candidate) {
  19. count++;
  20. }
  21. }
  22. return count * 2 > length ? candidate : -1;
  23. }
  24. }