基於索引數組排序整數數組？

Question

我們有兩個數組作爲輸入

數組1：[7,12,11,4]

ARRAY2：[1,3,2,0] - >這是索引陣列（即位置Array1（如果它是排序的）。

現在我們需要使用索引數組Array1排序Array1。

時間複雜度應該是O（N）

空間複雜度可以大於o（1），但應小於O（N）

，因爲就變成了O，則不應使用額外的陣列（ N）空間複雜度

Answer 1

考慮給出的數組是arr1和arr2。 排序陣列1爲每個數組2被存儲在「sortedArray」

下面給出

Java代碼：

int[] sortedArray = new int[arr1.length]; 
    for(int i=0;i<arr1.length;i++){ 
     int sourceIndex = arr2[i]; 
     sortedArray[i] = arr1[sourceIndex]; 
     } 

時間複雜度和空間複雜度：O（n）的

Answer 2

似乎你想要什麼下面的第二部分，您嘗試根據另一個排序一個數組。否則，我不知道爲什麼你不會直接對Array1進行排序。

一種方法是對基於Array2的'index'數組進行排序，然後使用它索引到Array1。 Java示例：

Integer[] idx = new Integer[arr2.length]; 
for(int i = 0 ; i < idx.length; i++) idx[i] = i;    
Arrays.sort(idx, new Comparator<Integer>() { 
    public int compare(Integer i1, Integer i2) {       
     return arr2[i1].compareTo(arr2[i2]); 
    }     
}); 

// arr2[idx[i]] is the sorted value of arr2 at index i 
// arr1[idx[i]] is the sorted value of arr1 corresponding to above at index i 

（請注意，您必須使用的，而不是INT整數或無法使用自定義的比較）

Answer 3

排序或安排基礎上在第二陣列提供索引給數組PLACE即O（1）的空間和O（K * n）的時間，其中k < N，N- =陣列的長度

void swapElement(int arr1[], int arr2[], int i, int arrj){ 
    int temp = arr1[i]; 
    arr1[i] = arr1[arrj]; 
    arr1[arrj] = temp; 

    temp = arr2[i]; 
    arr2[i] = arr2[arrj]; 
    arr2[arrj] = temp; 
} 

void sortArray(int arr1[], int arr2[], int n){ 
    int i=0; 
    for(;i<n;i++) 
    { 
     while(arr2[i]!=i){ 
      swapElement(arr1, arr2, i, arr2[i]); 
     } 
    } 

}