3

入力として2つの配列があります

配列 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

必要なのは、次の2番目の部分で、ある配列を別の配列に基づいて並べ替えようとしているようです。そうでなければ、なぜArray1を直接ソートしないのかわかりません。

1つの方法は、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

（intの代わりにIntegerを使用する必要があることに注意してください。そうしないと、カスタムコンパレータを使用できません。）

于 2013-02-26T06:12:49.303 に答える
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

sorting or arranging given array based on index provided in second array with IN PLACE i.e. O(1) space and O(k*n) time where k < n, n=length of array

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 に答える