java - 如何根据数组的内容顺序有效地修改数组的内容？

Question

我有一个关于数组的问题。例如，如果我知道数组的大小为 5，并且我的程序读取

[9993, 1000, 9992, 3, 872] 

进入数组，如何有效地编辑数组的内容，使其变为

[5, 3, 4, 1, 2]

我只能实现一个运行时间为 O(n^2) 的双 for 循环。我希望能找到更好的算法。

有什么提示吗？提前致谢!

Answer 1

一种选择是有一个像这样的类:

class Tuple implements Comparable<Tuple> {
    int value;  // value
    int pos;    // position in array

    public Tuple(int value, int pos) {
        this.value = value;
        this.pos = pos;
    }

    @Override
    public int compareTo(Tuple other) {  // sort based on values
        return Integer.compare(value, other.value);
    }
}

然后:

Tuple[] tups = new Tuple[array.length];

for (int i = 0; i < array.length; i++)
    tups[i] = new Tuple(array[i], i);

Arrays.sort(tups);

for (int i = 0; i < array.length; i++)
    array[i] = tups[i].pos + 1;

由于数组排序，这是一个 O(n log n) 的过程。