16.21. 交换和(中等)

Posted on Edited on In Views:

1，问题描述

面试题 16.21. 交换和

难度：中等

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

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

示例 1：

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

示例 2：

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

提示：

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

2，初步思考

​ 解法1：排序、交替比较

​ 解法2：空间换时间

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _16_21交换和 {

    // 空间换时间
    public int[] findSwapValues_area2time(int[] array1, int[] array2) {
        // 记录两个数组的和
        int sum1 = 0, sum2 = 0;
        // 记录 array2 中的数都出现过哪些
        Set<Integer> container = new HashSet<>();
        for (int num : array1) sum1 += num;
        for (int num : array2) {
            container.add(num);
            sum2 += num;
        }
        // 求两个数组之差
        int diff = sum1 - sum2;
        // 如果不是偶数差值，那么直接返回空数组
        if (diff % 2 != 0) return new int[]{};
        diff /= 2;
        // 从 array2 中找到能和 array1 中 num 配对的数，如果找到了就直接返回，没找到就返回空数组。
        for (int num : array1) {
            if (container.contains(num - diff)) {
                return new int[]{num, num - diff};
            }
        }
        return new int[]{};
    }

    // 暴力解法：
    public int[] findSwapValues(int[] array1, int[] array2) {
        Arrays.sort(array1);
        Arrays.sort(array2);
        int sum1 = 0, sum2 = 0;
        for (int i : array1) sum1 += i;
        for (int i : array2) sum2 += i;
        int diff = sum1 - sum2;// 差值
        if (diff % 2 != 0) return new int[]{};
        int target = Math.abs(diff) / 2;

        int idx1 = 0, idx2 = 0;
        while (idx1 < array1.length && idx2 < array2.length) {
            if (array1[idx1] > array2[idx2] + target) {
                idx2++;
            } else if (array1[idx1] == array2[idx2] + target) {
                return new int[]{array1[idx1], array2[idx2]};
            } else {
                idx1++;
            }
        }
        idx1 = 0;
        idx2 = 0;
        while (idx1 < array1.length && idx2 < array2.length) {
            if (array1[idx1] + target > array2[idx2]) {
                idx2++;
            } else if (array1[idx1] + target == array2[idx2]) {
                return new int[]{array1[idx1], array2[idx2]};
            } else {
                idx1++;
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        _16_21交换和 test = new _16_21交换和();
        int[] array1 = {4, 1, 2, 1, 1, 2};
        int[] array2 = {3, 6, 3, 3};

//        int[] array1 = {822, 717, 4226, 862, 450, 15, 242, 355, 282, 827};
//        int[] array2 = {65, 99, 23, 35, 66, 44, 98, 84};
        System.out.println(Arrays.toString(test.findSwapValues(array1, array2)));
    }
}