数组中需要进行的最小更改才能使连续元素的总和相同

Question

在线面试时问到这个问题：

有一个服务有 n 个服务器，第 i 个服务器的处理能力为 server[i] 个单位。

对于任何有效索引 i，用户可以将 k 个不同的任务分配给从索引 i 到 (i+k-1) 的任何连续服务器段。

为了确保行为一致，我们希望任何这些子数组的处理能力总和相等。

为了实现这一目标，我们可以用任何处理能力的新服务器替换任何服务器。

给定阵列服务器和整数 k，找到必须替换的最小服务器数量，以使 k 个服务器的每个连续子阵列具有相等的处理能力总和。

1. 示例 假设 n = 4，服务器 = [1, 2, 3, 2]，k = 2。

连续总和为 [(1,2), (2,3), (3,2)] = [3,5,5] 最好只替换第一台服务器 => [3,2,3,2] ，连续总和现在为 [(3,2), (2,3), (3,2)] = [5, 5,5] 所以答案是1。

2.示例假设 n = 5，服务器 = [1,2,1,1,2]，k = 3

连续总和 = [(1,2,1), (2,1,1), (1,1,2)] = [4,4,4]，所以答案是 0

这是代码：

      public static void main(String[] args) {
        System.out.println(solve(2, Arrays.asList(1,2,3,2))); // correct is 1
        System.out.println(solve(2, Arrays.asList(1,2,3))); // correct is 2
                System.out.println(solve(3, Arrays.asList(1,2,1,1,2))); // correct is 0
    }
      private static int solve(int k, List<Integer> server) {
       // here is my code, which fails for 2nd test case.
       long sum = 0;
       for(int i=0; i<k; i++) sum += server.get(i); // get sum of k items
       long current = sum; // assign that to current
       int result = 0;
       int n = server.size();
       for(int i=1; i<=n-k; i++) {
         current += server.get(i+k-1) - server.get(i-1); // get group sum that starts with i
         if(current != sum) result++; // found difference
         if(current > sum) sum = current; // update sum if it is less than current
       }
       return result; 
     }

在我的代码中，我假设对于以 i 开头的组，替换将仅在 server[i] 上完成，但此假设对于此任务来说是不正确的。解决这个问题的正确方法是什么。

Answer 1

子数组

server[i+1...i+k]

的总和等于

sum(server[i...i+k-1]) - server[i] + server[i + k]

（删除第一个元素并追加下一个元素）。

由于所有大小为

k

的子数组必须具有相等的总和，因此这直接意味着

server[i] = server[i + k]

。进一步应用相同的逻辑，我们可以发现对于所有整数 x，

server[i]

必须等于

server[i + x*k]

（其中

i + x*k

是有效索引）。换句话说，同一等价类模

k

中的所有索引的值必须全部相等。

然后，为了解决这个问题，我们可以简单地将同一等价类中的所有元素替换为该等价类中最常见的元素（请注意，有

k

模

k

不同的等价类）。这是

O(N)

，因为每个元素只处理一次。

static int solve(int k, List<Integer> server) {
    int minChanges = 0;
    for (int i = 0; i < k; i++) {
        var count = new HashMap<Integer, Integer>();
        int total = 0;
        for (int j = i; j < server.size(); j += k, ++total)
            count.merge(server.get(j), 1, Integer::sum);
        minChanges += total - Collections.max(count.values());
    }
    return minChanges;
}