从集合A和B中找到两个元素a和b，以便在交换这些元素时，集合的总和相等 [英] find two element a and b from set A and B such that on swapping these elements, sum of sets is equal

问题描述

设置A = [2，10，5，9] =总和[A] 26

Set A = [2, 10, 5, 9] = sum[A] 26

设置B = [1、10、4、9] =和[B] 24

Set B = [1, 10, 4, 9] = sum[B] 24

从集合A和B中找到两个元素a，b，使得

Find two elements a, b from set A and B such that

sum [A]-a + b =和[B]-b + a

sum[A] - a + b = sum [B] - b + a

我在O(n ^ 2)中解决了这个问题.

I solved this problem in O(n^2).

for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
        if(sumOfA - A[i] + B[j] == sumOfB + A[i] - B[j]){
            System.out.println("solution: " + A[i] + ", " + B[j])
            return;
        }
    }
}

如何将其改进为O(n)?

How it can be improved to O(n)?

推荐答案

将集合A的元素放入允许测试O(1)中的集合成员资格的结构(例如，哈希表或位向量，如果范围为的元素很小).这将在O(n)中运行.

Put the elements of set A into a structure that allows to test set membership in O(1) (for example a hash table or a bit vector if the range of elements is small). This will run in O(n).

现在遍历集合B，并检查A中是否有元素与B中的元素相距正确的距离(总和的一半).这也将在O(n)中进行.

Now iterate through the set B and check if there is an element in A that is the correct distance (half the difference of the sums) away from the element in B. This will also run in O(n).

这是一些伪代码，其中集合A的表示方式是contains操作在O(1)中运行:

Here is some pseudo code, where the set A is represented in such a way that the contains operation runs in O(1):

sumA = sum(A);
sumB = sum(B);
foreach (b in B) {
    a = b + (sumA - sumB)/2;
    if (A contains a) {
        return pair(a, b);
    }
}
return "no solution";

这篇关于从集合A和B中找到两个元素a和b，以便在交换这些元素时，集合的总和相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！