3

我们有两个数组作为输入

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

Array2:[1,3,2,0] --> 这是索引数组（即 Array1 排序后的位置）。

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

时间复杂度应该是 O(N)

空间复杂度可以大于 O(1) 但应该小于 O(N)

你不应该使用额外的数组，因为这会变成 O(N) 空间复杂度

4

3 回答 3

0

根据第二个数组中提供的索引对给定数组进行排序或排列，其中第二个数组具有 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]);
        }
    }

}
于 2013-02-26T06:20:33.510 回答
0

考虑给定的数组是 arr1 和 arr2。根据array2排序的array1存储在'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)

于 2013-02-26T06:09:49.593 回答
0

似乎您想要的是下面的第二部分，您正在尝试根据另一个数组对一个数组进行排序。否则，我不确定您为什么不直接对 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 ，否则您不能使用自定义比较器。）

于 2013-02-26T06:12:49.303 回答