Java中重新排列数组，使得所有相等索引的对应元素之和相同

给定两个长度为N的数组A[]和B[]。然后你的任务是重新排列两个数组的元素，使得所有 i (1 <= i <= N) 的总和(A i + B i )相同。如果不可能进行这样的安排，则输出-1。

例子：
输入： N = 3，A[] = {1, 2, 3}，B[] = {1, 2, 3}输出： A[] = {3, 1, 2}，B[] = {1, 3, 2}解释：重新排列后的 A[] 和 B[] 分别为 {3, 1, 2} 和​​ {1, 3, 2}。让我们看看每个索引 i 处的总和 (1 <= i <= 3)：

  • 第一个索引： A 1 + B 1 = (3 + 1) = 4
  • 第二个索引： A 2 + B 2 = (1 + 3) = 4
  • 第三个索引： A 3 + B 3 = (2 + 2) = 4

每个索引的总和是相同的。因此，安排是有效的并且遵循给定的约束。
输入： N = 3, A[] = {5, 6, 7}, B[] = {4, 3, 1}输出： -1解释：可以验证元素的排列不可能满足 (A i + B i ) 对于所有对。
方法：要解决该问题，请遵循以下思路：

使用HashMap就可以解决这个问题。有两件事需要检查：

  1. 重新排列的可能性
  2. 最终重排

让我们一一看看它们：
  • 重新排列的可能性：
    • 正如所提到的，对于 (1 <= i <= N)，所有 i 的 (A i + Bi ) 之和必须相等。仅当(Sum % N == 0) 时才可能将总和分布在 N 个索引上，其中 Sum 等于 A[] 和 B[] 的所有元素之和。因此，以这种方式可以检查布置的可能性。
  • 最终重组：
    • 首先，我们需要知道确切的平均总和，比如Avg，这样对于每个索引(A i + B i ) = Avg。
    • 由于 Sum 必须均匀分布在所有索引上，因此 Avg 将等于 (Sum/N)。形式上，Avg = (Sum/N)。
    • 现在，我们需要在 A[] 和 B[] 的元素之间进行配对，以便它们提供的对之和等于 Avg。考虑任何索引 i，我们知道一个元素，比如 A i，那么它必须与 B[] 的元素配对，使得 B i = (Avg – X)。因此， (A i + B i ) = ((X) + (Avg – X))的总和给出 Avg，这是该索引 i 处所需的总和。为了知道 B[] 中是否存在这样的 (Avg – X) 元素，我们需要实现一个常量检查实现。这只能通过将 B[] 的所有元素放入 HashMap 中来实现。因此，我们可以使用循环迭代所有索引，并且 Ai 可以与 Bi 配对，如果 Map 中存在 Bi ，则每次迭代时Bi的频率将减少 1。

分步算法：

  • 计算A[]和B[]所有元素的总和。
  • 如果总和不能被 N 整除，则返回 -1。
  • 否则计算平均值Avg = Sum/N。
  • 将 B[] 中所有元素的频率存储在频率图中。
  • 迭代 A[] 的所有元素，并针对每个索引 i，在频率图中搜索 (Avg – A)。
  • 如果未找到 (Avg – A)，则返回 -1。
  • 否则使 B = (Avg – A) 并继续。
  • 遍历完所有元素后，打印B[]数组作为最终答案。

下面是算法的实现：
// Java code to implement the approach

import java.util.*;

// Driver Class
class Main {

    // Driver Function
    public static void main(String[] args)
    {

        // Input
        int N = 3;
        int A[] = { 1, 2, 3 };
        int B[] = { 3, 1, 2 };

        // Function_call
        Rearrange(N, A, B);
    }
    public static void Rearrange(int N, int[] A, int[] B)
    {
        // 用于存储 B[] 元素的 HashMap
        HashMap<Integer, Integer> Map = new HashMap<>();

        //用于存储 A[] 和  B[] 中所有元素之和的变量
        int Sum = 0;

        // 同时计算总和并初始化地图中的元素
        for (int i = 0; i < N; i++) {
            Sum += A[i] + B[i];
            if (Map.containsKey(B[i])) {
                Map.put(B[i], Map.get(B[i]) + 1);
            }
            else
                Map.put(B[i], 1);
        }

        // 布尔变量用于将排列的可能性存储为 True 或 False
        boolean flag = true;

        // 如果可以安排
        if (Sum % N == 0) {
            // Caulating Avg as (Sum/N)
            int Avg = Sum / N;

            // 循环处理 A[] 中的元素，排列 B[] 中的元素
            for (int i = 0; i < N; i++) {

                // 需要与 A[i] 配对的元素
                int required = Avg - A[i];

                // 检查所需元素是否可用
                if (Map.containsKey(required)) {

                     // 如果可用，则用所需元素更新 B[i]，并将该元素的频率降低 1
                    B[i] = required;
                    Map.put(required,
                            Map.get(required) - 1);
                }
                // If there is not avaiability of required
                // element then mark flag as false
                else {
                    flag = false;
                }
            }
        }
      //如果 (Sum % N != 0) 标记为假，这是 If(Sum % N == 0)的其他情况
。        else
            flag = false;

        // 如果排列是可能的，那么打印重新排列 A[] 和 B[]
        if (flag) {
            for (int i = 0; i < N; i++) {
                System.out.print(A[i] + " ");
            }
            System.out.println();
            for (int i = 0; i < N; i++) {
                System.out.print(B[i] + " ");
            }
            System.out.println();
        }
        // 如果无法安排，则设置 -1。
        else
            System.out.println(-1);
    }
}

输出
1 2 3 
3 2 1 

时间复杂度： O(N)，其中N是输入数组A[]或B[]的大小。辅助空间： O(N)