程序员面试金典 - 面试题 16.21. 交换和

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

• 输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
• 输出: [1, 3]

示例:

• 输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
• 输出: []

提示：

• 1 <= array1.length, array2.length <= 100000

题目思考

1. 交换的元素需要满足什么要求?

解决方案

思路

• 分析题目, 假设我们交换数组 1 的 a 和数组 2 的 b, 那么数组 1 的和增加 b-a, 而数组 2 的和增加 a-b, 数组 2 的和相比数组 1 的和的差值增加(a-b)-(b-a) = 2*(a-b)
• 此时如果原来数组 2 的和相比数组 1 的和的差值恰好是-2*(a-b), 那么在交换 a 和 b 之后就做到了两个数组的和相同
• 所以我们可以先计算两个数组和的差值 diff:
  1. 如果该差值是奇数, 则一定没有可交换的数字对, 返回空数组, 因为任意交换都会产生偶数的差值
  2. 如果该差值是偶数, 则其一半就是所要交换的数字的差值. 这时候我们可以将两个数组转成集合 (一是避免重复处理相同数字, 二是提高查找效率), 然后遍历其中一个集合, 查看加上差值后的数字是否存在于另一个集合中, 存在的话则就是一组有效交换数字对
• 下面的代码对必要步骤有详细的解释, 方便大家理解

复杂度

• 时间复杂度 O(M+N): 需要求出两个数组的和, 并遍历其中一个数组
• 空间复杂度 O(M+N): 使用集合存储两个数组的元素

代码

class Solution:
    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
        # 先求出两个数组和的差值
        diff = sum(array2) - sum(array1)
        if diff & 1:
            # 如果差值是奇数, 一定无法通过交换来达到相等
            # 因为交换任意数字对得到的差值一定是两个数字差值的2倍
            return []
        # 然后将数组转成集合进行遍历, 避免重复处理相同数字
        v1, v2 = set(array1), set(array2)
        for x in v1:
            # y即为x需要交换的数字, 交换后array1增加diff/2, 而array2减少diff/2, 两个数组新的和正好相等
            y = x + diff // 2
            if y in v2:
                # y存在于array2中, 找到了有效数字对
                return [x, y]
        return []

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊