基于索引数组对整数数组进行排序？

Question

基于索引数组对整数数组进行排序？

arraysalgorithm

3

我们有两个输入数组。

数组1: [7,12,11,4]

数组2：[1,3,2,0] --> 这是索引数组（即如果对数组1进行排序，则为位置）。

现在我们需要使用索引数组Array2来对数组1进行排序。

时间复杂度应该为O（N）。

空间复杂度可以大于O（1），但应小于O（N）。

您不应使用额外的数组，因为那会导致O（N）的空间复杂度。

- Rajnikanth

听起来你已经对array1进行了排序。你的问题有些误导，因为现在你所需要做的就是使用array2作为索引来获取排序后的值。 - Andrew Mao

Array1尚未排序。例如：如果Array2已排序，它将告诉我们元素4将出现在索引0。希望现在清楚了。 - Rajnikanth

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- simpleJack · Answer 1

考虑给定的数组是arr1和arr2。按照arr2排序的数组1存储在“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)

- Andrew Mao · Answer 2

看起来你想要的是以下内容的第二部分，即你想要根据另一个数组对一个数组进行排序。否则，我不确定为什么你不直接对Array1进行排序。

一种方法是根据Array2对“索引”数组进行排序，然后使用它来索引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

（请注意，您必须使用Integer而不是int，否则无法使用自定义比较器。）

- rohitmb · Answer 3

根据第二个数组中提供的索引，使用IN 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]);
        }
    }

}