巧用哈希表:从 O(n^2) 到 O(n) 的优化|Java 刷题打卡

简介: 巧用哈希表:从 O(n^2) 到 O(n) 的优化|Java 刷题打卡

题目描述



这是 LeetCode 上的 888. 公平的糖果棒交换


Tag : 「哈希表」


爱丽丝和鲍勃有不同大小的糖果棒:A[i] 是爱丽丝拥有的第 i 根糖果棒的大小,B[j] 是鲍勃拥有的第 j 根糖果棒的大小。


因为他们是朋友,所以他们想交换一根糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)


返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。


如果有多个答案,你可以返回其中任何一个。


保证答案存在。


示例 1:


输入:A = [1,1], B = [2,2]
输出:[1,2]
复制代码


示例 2:


输入:A = [1,2], B = [2,3]
输出:[1,2]
复制代码


示例 3:


输入:A = [2], B = [1,3]
输出:[2,3]
复制代码


示例 4:


输入:A = [1,2,5], B = [2,4]
输出:[5,4]
复制代码


提示:


  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000
  • 1 <= A[i] <= 100000
  • 1 <= B[i] <= 100000
  • 保证爱丽丝与鲍勃的糖果总量不同。
  • 答案肯定存在。


朴素解法



最终目的是让两个数组总和相等。


我们可以先分别求得两个数组总和为 aSumaSumaSumbSumbSumbSum


即有数组总和 total=aSum+bSumtotal = aSum + bSumtotal=aSum+bSum


同时得数组目标总和 target=total/2target = total / 2target=total/2


当前两个数组与目标总和的差值分别为 target−aSumtarget - aSumtargetaSumtarget−bSumtarget - bSumtargetbSum


我们记 diff=target−aSumdiff = target - aSumdiff=targetaSum


对于某个 a[i]a[i]a[i] 而言,如果 a[i]a[i]a[i] 能构成答案,那么 b 数组中必然存在大小为 a[i]+diffa[i] + diffa[i]+diff 的值,使得两者交换后,数组总和均为 targettargettarget

因此我们只需要遍历数组 a,查找哪一个 a[i]a[i]a[i] 使得 a[i]+diffa[i] + diffa[i]+diff 存在于数组 b 即可。


代码:


class Solution {
    public int[] fairCandySwap(int[] a, int[] b) {
        int aSum = 0, bSum = 0;
        for (int i : a) aSum += i;  
        for (int i : b) bSum += i;  
        int total = aSum + bSum, target = total / 2;
        int diff = target - aSum;
        int[] ans = new int[2];
        for (int i : a) {
            if (find(b, i + diff)) {
                ans[0] = i;
                ans[1] = i + diff;
            }
        }
        return ans;
    }
    boolean find(int[] nums, int target) {
        for (int i : nums) {
            if (i == target) return true;
        }
        return false;
    }
}
复制代码


  • 时间复杂度: 计算总和复杂度为 O(n)O(n)O(n),找到最终解复杂度为 O(n2)O(n^2)O(n2)。整体复杂度为 O(n2)O(n^2)O(n2)
  • 空间复杂度:O(1)O(1)O(1)


查找优化



上述解法之所以无法做到线性,是因为我们每次都要对数组 b 进行扫描,确定 a[i]+diffa[i] + diffa[i]+diff 是否存在。


我们知道 map/set/数组 都可以实现 O(1)O(1)O(1) 查找,由于这里明确给出了两个数组中出现的数的范围,因此可以使用数组进行计数。


同时可以优化一下变量的使用,使用一个变量 diffdiffdiff 来计算最终的差异值。


这种优化,是典型的空间换时间做法。


代码:


class Solution {
    public int[] fairCandySwap(int[] a, int[] b) {
        // 先求得 a 的总和
        int diff = 0;
        for (int i : a) diff += i;  
        // 使用 cnt 统计 b 中的数的出现次数,同时计算 a 总和与 b 总和的差值
        int[] cnt = new int[100009];
        for (int i : b) {
            diff -= i;
            cnt[i]++;
        }
        // 计算出 a 中具体的替换差值是多少
        diff /= -2;
        int[] ans = new int[2];
        for (int i : a) {
            int target = i + diff;
            // 如果目标替换量在合法范围,并且存在于 b 数组中。说明找到解了
            if (target >= 1 && target <= 100000 && cnt[target] > 0) {
                ans[0] = i;
                ans[1] = target;
                break;
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:计算总和复杂度为 O(n)O(n)O(n),找到最终解复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n)O(n)O(n)
  • 空间复杂度:使用 cnt 数组进行计数。复杂度为 O(n)O(n)O(n)


最后



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


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


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


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

相关文章
|
15天前
|
Java Spring
如何优化Java异步任务的性能?
本文介绍了Java中四种异步任务实现方式:基础Thread、线程池、CompletableFuture及虚拟线程。涵盖多场景代码示例,展示从简单异步到复杂流程编排的演进,适用于不同版本与业务需求,助你掌握高效并发编程实践。(239字)
125 6
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
|
2月前
|
安全 Java 编译器
new出来的对象,不一定在堆上?聊聊Java虚拟机的优化技术:逃逸分析
逃逸分析是一种静态程序分析技术,用于判断对象的可见性与生命周期。它帮助即时编译器优化内存使用、降低同步开销。根据对象是否逃逸出方法或线程,分析结果分为未逃逸、方法逃逸和线程逃逸三种。基于分析结果,编译器可进行同步锁消除、标量替换和栈上分配等优化,从而提升程序性能。尽管逃逸分析计算复杂度较高,但其在热点代码中的应用为Java虚拟机带来了显著的优化效果。
63 4
|
2月前
|
存储 人工智能 算法
Java 大视界 -- Java 大数据在智能医疗影像数据压缩与传输优化中的技术应用(227)
本文探讨 Java 大数据在智能医疗影像压缩与传输中的关键技术应用,分析其如何解决医疗影像数据存储、传输与压缩三大难题,并结合实际案例展示技术落地效果。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据机器学习模型在生物信息学基因功能预测中的优化与应用(223)
本文探讨了Java大数据与机器学习模型在生物信息学中基因功能预测的优化与应用。通过高效的数据处理能力和智能算法,提升基因功能预测的准确性与效率,助力医学与农业发展。
|
2月前
|
数据采集 搜索推荐 Java
Java 大视界 -- Java 大数据在智能教育虚拟学习环境构建与用户体验优化中的应用(221)
本文探讨 Java 大数据在智能教育虚拟学习环境中的应用,涵盖多源数据采集、个性化推荐、实时互动优化等核心技术,结合实际案例分析其在提升学习体验与教学质量中的成效,并展望未来发展方向与技术挑战。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据在智能物流运输车辆智能调度与路径优化中的技术实现(218)
本文深入探讨了Java大数据技术在智能物流运输中车辆调度与路径优化的应用。通过遗传算法实现车辆资源的智能调度,结合实时路况数据和强化学习算法进行动态路径优化,有效提升了物流效率与客户满意度。以京东物流和顺丰速运的实际案例为支撑,展示了Java大数据在解决行业痛点问题中的强大能力,为物流行业的智能化转型提供了切实可行的技术方案。
|
存储 算法 Java
java- 分布式- 一致性哈希算法(1)
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。
1079 0
Java 数据库 Spring
59 0
|
1月前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
92 16

热门文章

最新文章