如何根據內容順序有效地修改數組的內容？

我有一個關於數組的問題。例如，如果我知道數組的大小爲5，和我的程序在如何根據內容順序有效地修改數組的內容？

[9993, 1000, 9992, 3, 872]

入陣讀，我怎麼能高效地編輯數組的內容，使得它成爲

[5, 3, 4, 1, 2]

我只能實現一個在O（n^2）運行的雙循環。我希望找到一個更好的算法。

任何提示？提前致謝！

來源

2013-09-21 boxme

您是否在嘗試構建排序？你可以通過構造一個包含整數'1 ... n'的輔助數組來在'O（n log n）'時間和'O（n）'空間中做到這一點，使用一個比較器對輔助數組進行排序，原始數組，然後將輔助數組複製到原始數組中。 – Jeremy

嗨Jeremy，但我不太明白如何使用比較器來引用回原始元素。您能詳細說明嗎？ – boxme

'如果（origArray [auxArray [i] -1] Jeremy

一種選擇是將有一類這樣的：

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）的過程中，由於數組排序。

來源

2013-09-21 17:00:30 arshajii

嗨Arshajii，你的算法會返回[4，5，2，3，1]。 – boxme

@boxme看到編輯，我剛剛在最後一行做了'tups [i] .pos + 1'。 – arshajii

爲了這個工作，你必須使用一種排序算法，因此，你將能夠得到的最佳運行時間是O（n logn）。如果您搜索它們，您可以在網上找到大量的排序算法。我推薦學習初學者的最快的是Quicksort，Mergesort和Heapsort。

來源

2013-09-21 17:40:49 user2802557

如何根據內容順序有效地修改數組的內容？

回答

相關問題