LeetCode1287

题目描述

给定一个非递减的整数数组 arr，其中有一个元素恰好出现超过数组长度的 25%。请你找到并返回这个元素。

示例

示例 1

输入:

arr = [1, 2, 2, 6, 6, 6, 6, 7, 10]

输出:

解释:

数组长度为 9，6 出现了 4 次，超过了 25%（即 2.25 次）。

示例 2

输入:

arr = [1, 1]

输出:

解释:

数组长度为 2，1 出现了 2 次，超过了 25%（即 0.5 次）。

思路分析

问题核心

我们需要找到一个在数组中出现次数超过数组长度 25% 的元素。

思路拆解

特殊情况处理：
- 如果数组长度为 1，直接返回该元素。
计算阈值：
- 计算数组长度的 25%，即 len / 4。
统计元素频率：
- 使用哈希表 Map 统计每个元素的出现次数。
判断是否超过阈值：
- 在统计过程中，如果某个元素的出现次数超过阈值，直接返回该元素。

代码段

class Solution {public int findSpecialInteger(int[] arr) {int len= arr.length;if(len==1)return arr[0];int num=len/4;Map<Integer,Integer> map=new HashMap<>();for (int count : arr) {int  temp=map.getOrDefault(count,0)+1;if(temp>num){return count;}else{map.put(count,temp);}}return -1;}
}

在这里插入图片描述

代码逐行讲解

1. 获取数组长度

int len = arr.length;

len 是数组的长度，用于后续计算阈值。

2. 特殊情况处理

if (len == 1)return arr[0];

如果数组长度为 1，直接返回该元素。

3. 计算阈值

int num = len / 4;

num 是数组长度的 25%，用于判断元素是否超过阈值。

4. 初始化哈希表

Map<Integer, Integer> map = new HashMap<>();

map 用于统计每个元素的出现次数。

5. 遍历数组

for (int count : arr) {

使用增强的 for 循环遍历数组中的每个元素。

6. 更新当前元素的频率

int temp = map.getOrDefault(count, 0) + 1;

temp 是当前元素的出现次数，初始值为哈希表中的值加 1。

7. 判断是否超过阈值

if (temp > num) {return count;
}

如果当前元素的出现次数超过阈值，直接返回该元素。

8. 更新哈希表

map.put(count, temp);

将当前元素的出现次数更新到哈希表中。

9. 返回默认值

return -1;

如果没有找到符合条件的元素，返回 -1。

复杂度分析

时间复杂度

遍历数组一次，时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度

使用了一个哈希表，最坏情况下需要存储所有元素的频率，因此空间复杂度为 O(n)。

总结的知识点

1. 哈希表的使用

使用 HashMap 统计元素的出现次数。

2. 边界条件处理

处理数组长度为 1 的特殊情况。

3. 增强的 `for` 循环

使用增强的 for 循环遍历数组。

4. 阈值计算

计算数组长度的 25%，用于判断元素是否超过阈值。

整合

class Solution {public int findSpecialInteger(int[] arr) {int len = arr.length; // 数组长度if (len == 1) // 特殊情况处理return arr[0];int num = len / 4; // 计算阈值Map<Integer, Integer> map = new HashMap<>(); // 哈希表统计频率for (int count : arr) { // 遍历数组int temp = map.getOrDefault(count, 0) + 1; // 更新当前元素的频率if (temp > num) { // 判断是否超过阈值return count;} else {map.put(count, temp); // 更新哈希表}}return -1; // 如果没有找到，返回 -1}
}