教3妹学编程: 888. 公平的糖果互换

手机软件开发 2024-9-19 17:55:41 135 0 来自 中国
3妹:"去吗?配吗?这褴褛的披风。战吗?战啊!以最卑微的梦。致那黑夜中的呜咽与咆哮。谁说站在光里的才算豪杰……"
3妹在慷慨鼓动的唱着孤勇者。
2哥:3妹,没想到你们女生也喜好《孤勇者》这首歌啊,我还以为只有男生喜好呢, 只是为什么你唱的这么伤心啊?
3妹:别提了,本日口试又被藐视了,问的算法题做出来了,但是口试官说复杂太高了,呜呜?。
2哥:问的什么标题啊,让我看一下?
标题

爱丽丝和鲍勃拥有差别总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ,aliceSizes 是爱丽丝拥有的第 i 盒糖果中的糖果数量,bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要相互互换一盒糖果,如许在互换之后,他们就可以拥有雷同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer,此中 answer[0] 是爱丽丝必须互换的糖果盒中的糖果的数量,answer[1] 是鲍勃必须互换的糖果盒中的糖果的数量。假如存在多个答案,你可以返回此中 任何一个 。标题测试用例包管存在与输入对应的答案。
示例 1:
输入:aliceSizes = [1,1], bobSizes = [2,2]
输出:[1,2]
示例 2:
输入:aliceSizes = [1,2], bobSizes = [2,3]
输出:[1,2]
示例 3:
输入:aliceSizes = [2], bobSizes = [1,3]
输出:[2,3]
示例 4:
输入:aliceSizes = [1,2,5], bobSizes = [2,4]
输出:[5,4]
提示:
1 <= aliceSizes.length, bobSizes.length <= 10^4
1 <= aliceSizes, bobSizes[j] <= 10^5
爱丽丝和鲍勃的糖果总数量差别。
标题数据包管对于给定的输入至少存在一个有效答案。
2哥:你是怎么做的呢?
3妹:就是双层for循环,找出互换的两个数总和相称就可以了。
方法一:

class Solution {    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {        int sum1 = 0;        for (int i = 0; i < aliceSizes.length; i++) {            sum1 += aliceSizes;        }        int sum2 = 0;        for (int i = 0; i < bobSizes.length; i++) {            sum2 += bobSizes;        }        int[] res = new int[2];        for (int i = 0; i < aliceSizes.length; i++) {            for (int j = 0; j < bobSizes.length; j++) {                if (sum1 - aliceSizes+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes) {                    return new int[] {                           aliceSizes, bobSizes[j]                    };                }             }        }        return new int[]{-1,-1};    }}2哥:解法是没错的,但是这个解法的时间复杂度是o(n^2), 简直挺高的,你以为有什么好的解法吗?
3妹:没有想到,忧郁啊。
思绪:

2哥:你看这个if表达式:if (sum1 - aliceSizes+bobSizes[j] == sum2 - bobSizes[j]+aliceSizes)
为true时, aliceSizes, bobSizes[j] 可以等价为: aliceSizes =( (sum1-sum2)/2) + bobSizes[j], 以是只要遍历bobSizes, 只要找到( (sum1-sum2)/2) + bobSizes[j] 的值在aliceSizes 中就可以了。
3妹:哦,这么奥妙,我怎么当时就没想到呢,我按照如许写一下。
方法二 java代码:

class Solution {    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {        int sumA = Arrays.stream(aliceSizes).sum();        int sumB = Arrays.stream(bobSizes).sum();        int delta = (sumA - sumB) / 2;        Set<Integer> rec = new HashSet<Integer>();        for (int num : aliceSizes) {            rec.add(num);        }        int[] ans = new int[2];        for (int y : bobSizes) {            int x = y + delta;            if (rec.contains(x)) {                ans[0] = x;                ans[1] = y;                break;            }        }        return ans;    }}
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2025-3-15 09:58, Processed in 0.136246 second(s), 32 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表