Как эффективно изменять содержимое массива в соответствии с его содержанием?

Question

У меня вопрос относительно массив. Например, если я знаю, что размер массива будет 5, а моя программа чтения в

[9993, 1000, 9992, 3, 872] 

в массив, как я могу изменить содержимое массива эффективно таким образом, что он становится

[5, 3, 4, 1, 2] 

Я могу реализовать только двойной цикл, который работает в O (n^2). Надеюсь найти для него лучший алгоритм.

Любые подсказки? Заранее спасибо!

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 (п журнал п) процесс, вследствие сортировки массива.

Answer 2

Для этого вы должны использовать один вид алгоритма сортировки, поэтому лучшим временем выполнения, которое вы сможете получить, является O (n logn). Существует множество алгоритмов сортировки, которые вы можете найти в Интернете, если их ищете. Самые быстрые из которых я бы рекомендовал для начинающих - Quicksort, Mergesort и Heapsort.