使两个数组的和相等的最短时间需求

Question

输入是两个数组，每个数组长度最多为6，数组中的每个元素都可以是1, 2, 3, 4, 5, 6之一。返回使两个数组之和相等所需改变的最小数量。

例如，A = [5, 4, 1, 2, 6, 5], B = [2]; 返回6，因为我们可以将A中的五个骰子变为[1, 1, 1, 1, 1, 1]，将B中的一个骰子变为[6]；然后两个数组就拥有相同的和。

首先，我会分别计算两个数组的总和：Sum(A) = 23, Sum(B) = 2。

然后暴力法是计算使和等于2、3、4，...，23所需的改变量。

但我认为时间复杂度太高了。

这个问题的难点在于我们不知道我们试图合并的目标和是多少。

尽管在给定的例子中，A的最小和为6，B的最大和值为6，因此我们知道它们将在6处重叠，所以我们可以裁剪其他分支。

- xiaokang lin

---

欢迎来到 SO！你可以分享一下你的解决尝试吗？这样社区里的人就可以更快地给你答案了。 - SomeDude

这里应该使用贪心算法。如果 sum(A) > sum(B)，则从 A 中获取最大元素和从 B 中获取最小元素，然后更改具有更多“潜力”的元素，然后重复此过程。这样，复杂度最多为 O(n²)，因为需要反复查找最小/最大值，并且可以通过首先对数组进行排序来减少复杂度。 - tobias_k

你好，当你改变那个具有更多“潜力”的元素后，我们会使排序无效，并将修改后的元素调整到适当的位置并重复此过程。 - xiaokang lin

当然，您会使排序无效，但是您也知道您已经查看过哪些元素，因此您可以按排序顺序迭代元素，并不关心您已更改的元素。 - tobias_k

Answer 1

一个贪心算法能够很好地解决这个问题：

• 确定哪个数组的和更大，哪个更小
• 可选：对数组进行排序以使后续步骤更快
• 当总和不相等时：
  • 从较大的数组中获取最大元素，从较小的数组中获取最小元素
  • 确定哪个具有更多的“潜力”来平衡总和，例如在“较大”的数组中的 5 可以变成 1，或者在较小的数组中的 3 可以变成 6
  • 选择具有更多“潜力”的元素并将其更改（一直到 1 或 6，或者根据需要更改）

如果没有排序，则复杂度最多为 O(n²) ，因为要重复查找最小和最大元素，并且通过对数组进行一次排序，可以将其降低到 O(n logn) ，然后只需按顺序迭代元素即可。（您不必重新排序数组或重新计算总和，因为您知道更改了哪些元素以及如何更改它们，您不必再次查看这些元素。）

- tobias_k

---

当可能值的集合是固定的，比如范围在1到6之间（正如这里的情况），可以很容易地用O（n）进行排序。甚至不需要严格排序：只需计算每种类型的值的数量（这就是计数排序，没有实际的排序步骤）。虽然如果输入大小固定且较小（这似乎也是这里的情况），复杂度大规模无意义。 - Bernhard Barker

Answer 2

• 考虑完全无法解决的情况
• 不要对数组进行排序，而是构建两个大小为6的映射表（这需要O（N）来构建，查找将是O（1）），然后计算总和
• 然后对差值应用贪心算法，通过最大步长等移动，直到差值为零（再次复杂度为O（N））

总体复杂度为O（N）

Python代码：

    def _cast_to_dict(A):
        initial_dict = {i: 0 for i in range(1, 7)}
        total_sum = 0
        for a in A:
            total_sum += a
            initial_dict[a] += 1
        return initial_dict, total_sum      
    
    def solution(A, B):
        if len(A) > 6 * len(B) or len(B) > 6 * len(A):
             # Case where the problem is not solvable
            raise ValueError("Impossible to achieve")
        state_of_A, sum_A = _cast_to_dict(A)
        state_of_B, sum_B = _cast_to_dict(B)
    
        total_moves = 0
        if sum_A == sum_B:
            return 0
        elif sum_A < sum_B:
            state_of_A, state_of_B = state_of_B, state_of_A
            sum_A, sum_B = sum_B, sum_A
        # Now we can assume sum_A > sum_B
        # to reduce the diff, we can either increase B or decrease A
        diff = sum_A - sum_B
    
        print('DIFF %i' % diff)
        possible_jumps = {5: [(6, 1)], 4:[(6, 2), (5, 1)], 3:[(6, 3), (5, 2), (4, 1)], 2:[(6, 4), (5, 3), (4, 2), (3, 1)], 1:[(6, 5), (5, 4), (4, 3), (3, 2), (2, 1)]}
        while diff > 0:
            max_diff_to_jump = min(5, diff)
            for possible_jump in range(max_diff_to_jump, 0, -1):
                is_jump_realized = False
                print('Possible jump %i' % possible_jump)
                for swap in possible_jumps[possible_jump]:
                    if state_of_A[swap[0]] > 0:
                        print('flipping A with (%s, %s)' % swap)
                        state_of_A[swap[0]] -= 1
                        state_of_A[swap[1]] += 1
                        diff -= possible_jump
                        total_moves += 1
                        is_jump_realized = True
                        break
                    elif state_of_B[swap[1]] > 0:
                        print('flipping B with (%s, %s).T' % swap)
                        state_of_B[swap[1]] -= 1
                        state_of_B[swap[0]] += 1
                        diff -= possible_jump
                        total_moves += 1
                        is_jump_realized = True
                        break                  
                if is_jump_realized:
                        break
        return total_moves

- Matt

Answer 3

正如您使用标签所提到的那样，贪心算法可以得出一个简单的解决方案。 我们假设A的总和大于B的总和。

然后，我们首先考虑修改A中最大的元素和B中最小的元素。这可以通过先对这两个数组进行排序（也可以使用最大堆和最小堆）来实现。

以下是C++代码，由于非常简单，我相信您很容易理解。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int n_changes (std::vector<int> &A, std::vector<int> &B) {
    int sum_A = std::accumulate (A.begin(), A.end(), 0);
    int sum_B = std::accumulate (B.begin(), B.end(), 0);
    
    if (sum_A == sum_B) return 0;
    if (sum_A < sum_B) {
      std::swap (A, B);
      std::swap (sum_A, sum_B);
    }
    
    std::sort (A.begin(), A.end(), std::greater<int>());
    std::sort (B.begin(), B.end());
    int nA = A.size();
    int nB = B.size();
    
    int count = 0;
    int iA = 0;
    int iB = 0;
    int candidate_A, candidate_B;
    while (sum_A > sum_B) {
        if (iA < nA) candidate_A = A[iA]; else candidate_A = 1;
        if (iB < nB) candidate_B = B[iB]; else candidate_B = 6;
        if ((candidate_A == 1) && (candidate_B == 6))  break;
        count ++;
        if ((candidate_A -1) > (6 - candidate_B)) {
            iA++;
            sum_A += (1 - candidate_A);
        } else {
            iB++;
            sum_B += (6 - candidate_B);
        }
    }
    if (sum_A > sum_B) count = -1;
    return count;
}

int main() {
    std::vector<int> A = {5, 4, 1, 2, 6, 5};
    std::vector<int> B = {2};

    std::cout << n_changes (A, B) << "\n";
}

- Damien

---

@lamnguyen 感谢您的修订。我在文本中提到“让我们假设A的总和大于B的总和”，但实际上这种表述更好。 - Damien

Answer 4

这里有一份关于代码逻辑的说明。

def changes_to_equal_sums(a, b):
    # organize into dict so we can determine what list has the bigger sum
    sums = {
        sum(a): a,
        sum(b): b
    }
    # get the bigger sum list and sort it in descending order
    big_sum_dice = sorted(sums[max(sums.keys())], reverse=True)
    # get the smaller sum list and sort it in ascending order
    small_sum_dice = sorted(sums[min(sums.keys())])
    # calculate the delta/distance we need to equalize between the two sums
    dist = sum(big_sum_dice) - sum(small_sum_dice)
    # count the number of changes we have made
    count = 0
    # pointer to the last index in the big_sum_dice list
    last_big = 0
    # pointer to the last index in the small_sum_dice list
    last_small = 0

    # a while loop that will run when the sums aren't equal and while we didn't run out of index range (of both lists)
    while sum(big_sum_dice) != sum(small_sum_dice) and len(big_sum_dice)+len(small_sum_dice) > last_small+last_big:

        # choose more efficient element to change -
        # the most efficient elements to change are:
        # - from the big_sum_list, the numbers closer to 6
        # - from the small_sum_list, the numbers closer to 1
        if len(small_sum_dice) <= last_small or big_sum_dice[last_big] - 1 > 6 - small_sum_dice[last_small]:
            # check if the margin of the given number allows us to finally equalize the sums
            if dist < big_sum_dice[last_big]:
                count+=1
                big_sum_dice[last_big] = big_sum_dice[last_big] - dist
            # if not so we change the margin to the extreme - which is 1
            else:
                dist = dist - (big_sum_dice[last_big] -1)
                big_sum_dice[last_big] = 1
                count +=1
                last_big +=1
        else:
            # check if the margin of the given number allows us to finally equalize the sums
            if dist < 6-small_sum_dice[last_small]:
                count+=1
                small_sum_dice[last_small] = small_sum_dice[last_small] + dist
            # if not so we change the margin to the extreme - which is 6
            else:
                dist = dist - (6 - small_sum_dice[last_small])
                small_sum_dice[last_small] = 6
                count+=1
                last_small+=1

    # in case of no possible option (for ex. [1] [1,1,1,1,1,1,1]) return -1
    if sum(big_sum_dice) != sum(small_sum_dice):
        return -1
    return count


# for ex. :

A = [5, 4, 1, 2, 6, 5]
B = [2]
print(changes_to_equal_sums(A,B))

- Ben Hazout

Answer 5

这里是Java的解决方案。记得先将int数组改为Integer数组。因为int数组不能用于 array.sort(comparator)。

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class TwoDice {
    public static void main (String args[]) {
        int A1[] = {5}, B1[] = {1,1,6};
        int A2[] = {2,3,1,1,2}, B2[] = {5,4,6}; 
        int A3[] = {5,4,1,2,6,5}, B3[] = {2}; 
        int A4[] = {1,2,3,4,3,2,1}, B4[] = {6};
        int A5[] = {1,1,1}, B5[] = {2};
        int A6[] = {5,4,4,2,6,5}, B6[] = {2}; 
        int A7[] = {1}, B7[] = {2,2,2,2,2,2};  
        
        System.out.println(solution(A1,B1));
        System.out.println(solution(A2,B2));
        System.out.println(solution(A3,B3));
        System.out.println(solution(A4,B4));
        System.out.println(solution(A5,B5));
        System.out.println(solution(A6,B6));
        System.out.println(solution(A7,B7));
    }
    
    public static int solution(int []A, int[]B ) {  
        Integer []A_new = changeToInteger(A);
        Integer []B_new = changeToInteger(B);
        
        int sum_A = getSum(A_new);
        int sum_B = getSum(B_new);
        if (sum_A == sum_B) return 0;
        
        if(sum_A < sum_B) {
            int temp = sum_A;
            sum_A = sum_B;
            sum_B = temp;
            
            Object temp_array = A_new;
            A_new = B_new;
            B_new = (Integer[]) temp_array;
        }
        
        //Array A -> Descending sort
        Arrays.sort(A_new, new Comparator<Integer>() {
               @Override
               public int compare(Integer o1, Integer o2) {
                   return o2-o1;
              } 
            });
        //Array B -> Ascending sort
        Arrays.sort(B_new);

        int nA = A_new.length;
        int nB = B_new.length;      
        if(nA * 1 > nB * 6 ) return -1;
        
        int count = 0;
        int iA = 0, iB = 0; 
        int candidate_A, candidate_B;
        
        while (sum_A > sum_B) {
            if (iA < nA) candidate_A = A_new[iA]; else candidate_A = 1; 
            if (iB < nB) candidate_B = B_new[iB]; else candidate_B = 6; 
            if ((candidate_A == 1) && (candidate_B == 6) )  break;
            count ++;
            if ((candidate_A -1) > (6 - candidate_B)) {
                iA++;
                sum_A += (1 - candidate_A);
            } else {
                iB++;
                sum_B += (6 - candidate_B);
            }
        }
        return count;
    }
    
    public static int getSum(Integer []num) {
        int sum = 0;
        for(int i: num) {
            sum += i;
        }
        return sum;
    }
    
    public static Integer[] changeToInteger(int []nums) {
        IntStream stream = Arrays.stream(nums);
        Stream<Integer> integerStream = stream.boxed();
        Integer[] integers = integerStream.toArray(Integer[]::new);
        return integers;
    }

}

- Frenkie Wang