⭐ 题目日期：

腾讯 - 25届秋招

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝思路分析：

方法一：用哈希表直接统计各个元素出现的次数，再遍历哈希表，寻找出现次数超过一半的元素。

1. 时间复杂度：O(n)， 遍历数组 + 哈希表

2. 空间复杂度：O(n), 用于哈希表存储数据

方法二：将数组排序，再线性扫描数组，判断是否有一元素连续出现的次数超过半数

1. 时间复杂度：O(nlogn)， 排序

2. 空间复杂度：O(logn), 取决于所选的排序算法，如选择高效的排序算法 快速排序，平均空间复杂度来自于递归栈的调用 O(logn)

方法三[最优解]：摩尔投票算法；摩尔投票的核心思想是选一个候选人(初始可以为数组的第一个元素)和一个计数器, 遍历数组，如果当前元素与候选人相同，计数器加一；否则计数器减一。当计数器为零时，更换候选人为当前元素，计数器重置为 1。第一次遍历后得到的候选人可能不是多数元素，因此需要再次遍历数组，验证候选人出现的次数是否超过一半。

1. 时间复杂度：O(n)， 遍历数组两遍

2. 空间复杂度：O(1)

💻代码 1：

Java

// 返回超过半数的数，若不存在，返回Integer.MIN_VALUE
public int frequentNum(int[] nums) {
 if (nums == null || nums.length == 0) {
     return Integer.MIN_VALUE;
 }

 Map<Integer, Integer> map = new HashMap<>();
 for (int num : nums) {
     map.put(num, map.getOrDefault(num, 0) + 1);
 }

 for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
     if (entry.getValue() > nums.length / 2) {
         return entry.getKey();
     }
 }

 return Integer.MIN_VALUE;
}

💻代码 2：

Java

// 返回超过半数的数，若不存在，返回Integer.MIN_VALUE
public int frequentNum(int[] nums) {
 if (nums == null || nums.length == 0) {
     return Integer.MIN_VALUE;
 }

 Arrays.sort(nums);
 int potentialTarget = nums[nums.length / 2];
 int count = 0;
 for (int num : nums) {
     if (num == potentialTarget) {
         count++;
     }
 }

 return count > nums.length / 2 ? potentialTarget : Integer.MIN_VALUE;
}

💻代码 3：

Java

// 返回超过半数的数，若不存在，返回Integer.MIN_VALUE
public int frequentNum(int[] nums) {
 if (nums == null || nums.length == 0) {
     return Integer.MIN_VALUE;
 }

 int candidate = nums[0];
 int count = 1;

 for (int i = 1; i < nums.length; i++) {
     if (nums[i] == candidate) {
         count++;
     } else {
         count--;
         if (count == 0) {
             candidate = nums[i];
             count = 1;
         }
     }
 }

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

 return count > nums.length / 2 ? candidate : Integer.MIN_VALUE;
}