基于索引数组排序整数数组？

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]); 
     } 
    } 

}