数组元素映射至排序后位置的面试解法及复杂度分析

核心思路 #

要搞定这个问题，核心就是先记清楚每个元素在排序后的数组里的所有位置，再按原数组的顺序挨个取对应的位置。因为数组里有重复元素，不能直接用哈希表存单个索引，得给每个元素存个索引列表（或队列），按排序后的顺序存放，这样原数组里重复的元素就能依次拿到排序后的对应位置——比如示例里的两个33，第一个拿排序后的第2位，第二个拿第3位。

具体步骤拆解：

• 先把原数组排序，得到排序后的版本。
• 遍历排序后的数组，用哈希表给每个元素存它出现的所有索引（按顺序存入）。
• 再遍历原数组，对每个元素，从哈希表的对应列表里按顺序取出第一个可用的索引，放进结果数组即可。

修正后的完整实现 #

你现在写的代码已经完成了前两步，只差最后生成结果数组的环节。下面是补全后的完整Java代码：

import java.util.*;

public class ElementPositionMapper {
    public static Map<Integer, Queue<Integer>> findAllPositions(List<Integer> input) {
        Map<Integer, Queue<Integer>> result = new HashMap<>();
        List<Integer> sortedInput = new ArrayList<>(input);
        Collections.sort(sortedInput);

        for (int i = 0; i < sortedInput.size(); i++) {
            int num = sortedInput.get(i);
            // 简化逻辑：key不存在则创建新队列，再加入当前索引
            result.computeIfAbsent(num, k -> new LinkedList<>()).add(i);
        }
        return result;
    }

    public static List<Integer> getPositionMapping(List<Integer> input) {
        Map<Integer, Queue<Integer>> positionMap = findAllPositions(input);
        List<Integer> result = new ArrayList<>(input.size());
        for (int num : input) {
            // 取出当前元素对应的下一个排序位置，队列poll()直接拿第一个元素
            result.add(positionMap.get(num).poll());
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> input = Arrays.asList(33, 44, 33, 11, 22);
        List<Integer> output = getPositionMapping(input);
        System.out.println(output); // 输出 [2, 4, 3, 0, 1]
    }
}

实现细节说明 #

• 把原代码里的List<Integer>换成Queue<Integer>，用poll()可以直接取出队列的第一个元素，不用手动维护列表指针，更高效简洁。
• 新增的getPositionMapping方法补全了你缺失的关键步骤：遍历原数组，将每个元素对应的排序位置取出并拼成结果数组。
• 用computeIfAbsent替代手动判断containsKey，代码更简洁，逻辑也更清晰。

时间&空间复杂度 #

• 时间复杂度：

  • 排序数组的时间是O(n log n)，这是整个流程的性能瓶颈。
  • 遍历排序数组构建哈希表、遍历原数组生成结果的时间都是O(n)。
    整体时间复杂度为O(n log n)。

• 空间复杂度：

  • 排序后的数组占O(n)空间，哈希表存储所有元素的索引总空间也是O(n)，结果数组同样占O(n)空间。
    整体空间复杂度为O(n)。

其他可选思路 #

如果数组元素的取值范围不大（比如都是0~1000的整数），可以用计数排序的思路优化：

1. 找出数组的最小值和最大值，统计每个元素的出现次数。
2. 计算前缀和，得到每个元素在排序后的起始位置。
3. 遍历原数组，对每个元素，用起始位置加上该元素已被使用的次数作为它的排序位置，随后更新已使用次数。
   这种方法的时间复杂度能降到O(n + m)（m是元素的取值范围），但仅适合元素范围较小的场景。

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