LeetCode1287

LeetCode1287 目录 题目描述示例思路分析代码段代码逐行讲解复杂度分析总结的知识点整合总结

---

题目描述

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

---

示例 示例 1

输入:

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

输出:

6

解释:

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

---

示例 2

输入:

arr = [1, 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 } }

---

总结

通过哈希表统计元素的出现次数，并在遍历过程中判断是否超过阈值，能够高效地解决问题。代码逻辑清晰，复杂度控制在合理范围内，适合面试或竞赛场景。希望这个分析对你有帮助！