将每个元素映射到其在数组中的位置，就好像它已排序

Question

我目前正在准备编码面试，我想知道其他人对这个问题有什么看法。

将每个元素映射到它在数组中的位置 如果它被排序。现在我们需要返回一个新数组，其中每个元素都映射到它的 排序数组中的位置。

• 输入：

  [33, 44, 33, 11, 22]

• 输出：

  [2, 4, 3, 0, 1]

[11, 22, 33, 33, 44]

（如果它被排序会是什么样子）

对于时间和空间的复杂性，您的方法和解决方案是什么？

我得到的最远的是：

public static Map<Integer, List<Integer>> findAllPositions(List<Integer> input) {
    Map<Integer, List<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);
        if (!result.containsKey(num)) {
            result.put(num, new ArrayList<>());
        }
        result.get(num).add(i);
    }
    return result;
}

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

Answer 1

根据你的代码修改

  public static List<Integer> findAllPositions(List<Integer> input) {
    Map<Integer, List<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);
      if (!result.containsKey(num)) {
        result.put(num, new ArrayList<>());
      }
      result.get(num).add(i);
    }

    List<Integer> result2 = new ArrayList<>();
    for (int j = 0; j < input.size(); j++) {
      List<Integer> tmp =result.get(input.get(j));
      if (tmp != null && tmp.size() > 0) {
        result2.add(tmp.get(0));
        tmp.remove(0);
      }
    }
    return result2;
  }

  public static void main(String[] args) {
    List<Integer> input = Arrays.asList(33, 44, 33, 11, 22);
    System.out.println(findAllPositions(input));
  }