Java中如何基于已排序数组对另一个关联数组执行重排序操作

• 给定存在重复元素的未排序原始数组：int [] nums = {8,1,2,2,3}，排序后结果为[1,2,2,3,8]
• 已有的count数组：int[] count = {0,1,1,3,4}是基于排序后的nums计算得到，每个下标位置的count值对应排序后nums同下标元素的统计结果
• 目标是将count数组按照nums从未排序到排序的下标映射关系反向重排，最终得到count结果为[4,0,1,1,3]

实现逻辑 #

你需要的核心能力是先记录「原始nums每个位置的元素，在排序后nums中对应的唯一下标」，处理重复元素时通过占用标记避免匹配冲突，再通过这个下标映射把和排序数组绑定的count数组，还原为和原始未排序数组位置对应的结果。

Java 实现代码 #

import java.util.Arrays;

public class ReorderDemo {
    public static void main(String[] args) {
        // 原始未排序nums
        int[] originalNums = {8,1,2,2,3};
        // 排序后的nums副本
        int[] sortedNums = Arrays.copyOf(originalNums, originalNums.length);
        Arrays.sort(sortedNums);
        // 对应排序后nums的count数组
        int[] count = {0,1,1,3,4};

        // 构建下标映射：key是原始nums下标，value是对应元素在排序后nums的下标
        boolean[] used = new boolean[sortedNums.length];
        int[] indexMap = new int[originalNums.length];
        for (int i = 0; i < originalNums.length; i++) {
            for (int j = 0; j < sortedNums.length; j++) {
                if (originalNums[i] == sortedNums[j] && !used[j]) {
                    indexMap[i] = j;
                    used[j] = true;
                    break;
                }
            }
        }

        // 重排count数组
        int[] reorderedCount = new int[count.length];
        for (int i = 0; i < originalNums.length; i++) {
            reorderedCount[i] = count[indexMap[i]];
        }

        // 输出结果：[4, 0, 1, 1, 3]
        System.out.println(Arrays.toString(reorderedCount));
    }
}

如果你需要封装成类似你给出的伪代码的工具方法，可以使用如下封装版本：

import java.util.Arrays;

public class ArrayUtils {
    public static void reorder(int[] targetArr, int[] originalArr, int[] sortedArr) {
        boolean[] used = new boolean[sortedArr.length];
        int[] indexMap = new int[originalArr.length];
        for (int i = 0; i < originalArr.length; i++) {
            for (int j = 0; j < sortedArr.length; j++) {
                if (originalArr[i] == sortedArr[j] && !used[j]) {
                    indexMap[i] = j;
                    used[j] = true;
                    break;
                }
            }
        }
        int[] temp = Arrays.copyOf(targetArr, targetArr.length);
        for (int i = 0; i < targetArr.length; i++) {
            targetArr[i] = temp[indexMap[i]];
        }
    }

    // 调用示例
    public static void main(String[] args) {
        int[] originalNums = {8,1,2,2,3};
        int[] sortedNums = Arrays.copyOf(originalNums, originalNums.length);
        Arrays.sort(sortedNums);
        int[] count = {0,1,1,3,4};
        reorder(count, originalNums, sortedNums);
        System.out.println(Arrays.toString(count)); // 输出[4, 0, 1, 1, 3]
    }
}

内容的提问来源于stack exchange，提问作者abhinit21