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

代码段

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
    }
}

总结

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