「数组计数」 & 「哈希表计数」解法,以及该如何选择两者 | Java 刷题打卡

简介: 「数组计数」 & 「哈希表计数」解法,以及该如何选择两者 | Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 697. 数组的度 ,难度为 简单


Tag : 「哈希表」


给定一个非空且只包含非负数的整数数组 nums,数组的度的定义是指数组里任一元素出现频数的最大值。


你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。


示例 1:


输入:[1, 2, 2, 3, 1]
输出:2
解释:
输入数组的度是2,因为元素1和2的出现频数最大,均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2,所以返回2.
复制代码


示例 2:


输入:[1,2,2,3,1,4,2]
输出:6
复制代码


提示:


  • nums.length 在1到 50,000 区间范围内。
  • nums[i] 是一个在 0 到 49,999 范围内的整数。


数组计数



网络异常,图片无法展示
|


由于已知值的范围是 [0, 49999]


我们可以使用数组 cnt 来统计每个值出现的次数,数组 firstlast 记录每个值「首次出现」和「最后出现」的下标。


同时统计出最大词频为 max


然后再遍历一次数组,对于那些满足词频为 max 的数值进行长度计算。


class Solution {
    int N = 50009;
    public int findShortestSubArray(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[N];
        int[] first = new int[N], last = new int[N];
        Arrays.fill(first, -1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            max = Math.max(max, ++cnt[t]);
            if (first[t] == -1) first[t] = i;
            last[t] = i;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (cnt[t] == max) ans = Math.min(ans, last[t] - first[t] + 1);
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:对数组进行常数次扫描。复杂度为 O(n)O(n)
  • 空间复杂度:O(n)O(n)


哈希表计数



网络异常,图片无法展示
|


同样的,除了使用静态数组,我们还可以使用哈希表进行计数。


class Solution {
    public int findShortestSubArray(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>(), last = new HashMap<>();
        int max = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            cnt.put(t, cnt.getOrDefault(t, 0) + 1);
            max = Math.max(max, cnt.get(t));
            if (!first.containsKey(t)) first.put(t, i);
            last.put(t, i);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (cnt.get(t) == max) {
                ans = Math.min(ans, last.get(t) - first.get(t) + 1);
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:对数组进行常数次扫描。复杂度为 O(n)O(n)
  • 空间复杂度:O(n)O(n)


总结



我们知道 哈希表 = 哈希函数 + 数组,由于哈希函数计算需要消耗时间(Java 中首先涉及自动装箱/拆箱,之后还要取对象的 hashCode 进行右移异或,最后才计算哈希桶的下标),以及处理哈希冲突的开销。


其效率必然比不上使用我们静态数组进行计数。


因此我建议,对于那些 数值范围确定且不太大(10^6106 以内都可以使用,本题数量级在 10^4104 的计算场景,使用数组进行计数,而不是使用哈希表。


最后



这是我们「刷穿 LeetCode」系列文章的第 No.697 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
21天前
|
Java
Java 数组学习笔记
本文整理Java数组常用操作:遍历、求和、查找、最值及二维数组行求和等典型练习,涵盖静态初始化、元素翻倍、去极值求平均等实例,帮助掌握数组基础与应用。
|
2月前
|
存储 缓存 Java
Java数组全解析:一维、多维与内存模型
本文深入解析Java数组的内存布局与操作技巧,涵盖一维及多维数组的声明、初始化、内存模型,以及数组常见陷阱和性能优化。通过图文结合的方式帮助开发者彻底理解数组本质,并提供Arrays工具类的实用方法与面试高频问题解析,助你掌握数组核心知识,避免常见错误。
|
3月前
|
存储 Java 索引
java 数组
在 Java 中,数组是一种数据结构,用于存储多个相同类型的数据元素。数组的大小一旦创建后就不能改变,因此它是固定长度的。Java 数组是一种 对象,即使它存储的值是基本类型(如 int、double 等),它也是一个对象引用。
81 0
|
5月前
|
存储 人工智能 Java
打乱数组内容引发的问题( Java)
本文介绍了两种实现数组随机打乱的方法,并深入探讨了Java中原始数据类型与对象类型的差异。方法一通过自定义随机数交换数组元素位置,方法二借助`Collections.shuffle()`函数完成数组打乱。同时,文章详细解析了`int`和`Integer`的区别,包括声明方式、内存占用、初始化以及对象特性等,并讲解了自动装箱与拆箱的功能,帮助读者更好地理解Java的基础知识。
|
6月前
|
存储 Java 数据挖掘
Java 中数组的多种定义方式
本文深入解析了Java中数组的多种定义方式,涵盖基础的`new`关键字创建、直接初始化、动态初始化,到多维数组、`Arrays.fill()`方法以及集合类转换为数组等高级用法。通过理论与实践结合的方式,探讨了每种定义方法的适用场景、优缺点及其背后的原理,帮助开发者掌握高效、灵活的数组操作技巧,从而编写更优质的Java代码。
219 0
|
7月前
|
人工智能 Java
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
376 1
Java 中数组Array和列表List的转换
|
7月前
|
存储 Java 索引
Java 复制数组
本文介绍了Java中数组的基础知识与常用操作,包括数组的概念、创建、访问元素、遍历、复制、排序和搜索等方法。同时详细讲解了数组的五种赋值方式,并通过代码示例演示了求总和平均值、最大最小值、升序降序排序及Arrays类的常用方法。内容深入浅出,适合初学者学习掌握Java数组的核心功能与应用场景。
|
7月前
|
存储 监控 Java
《从头开始学java,一天一个知识点》之:数组入门:一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间?** - 看了三天教程,连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;,大脑突然空白 - 写出的代码总是莫名报NPE,却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」!我们承诺:每天1分钟,地铁通勤、午休间隙即可完成学习;直击痛点,只讲高频考点和实际开发中的「坑位」;拒绝臃肿,没有冗长概念堆砌,每篇都有可运行的代码标本。明日预告:《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧,帮助你快速掌握Java数组的精髓。
134 23
|
9月前
|
存储 Java C++
Java数组:静态初始化与动态初始化详解
本文介绍了Java中数组的定义、特点及初始化方式。
471 12

热门文章

最新文章