重新排列數組,如果'arr [i]'為'j',則'arr [j]'變為'i'  


難度級別 容易獎學金
經常問 亞馬遜 德里韋里 庫利扎 長郎 Opera 瀏灠器 時代互聯網 朝聖
排列

問題陳述  

問題“如果'arr [i]'為'j',重新排列數組,使'arr [j]'變為'i'”,說明您有一個 “ n” 包含整數的大小數組。 數組中的數字範圍為0到n-1。 問題陳述要求以數組[i] = j變為arr [j] = i的方式重新排列數組。

例  

arr[]={1,3,5,2,0,4}
4 0 3 1 5 2

解釋

將arr [0] = 1更改為arr [1] = 0

將arr [1] = 3更改為arr [3] = 1

將arr [2] = 5更改為arr [5] = 2

將arr [3] = 2更改為arr [2] = 3

將arr [4] = 0更改為arr [0] = 4

將arr [5] = 4更改為arr [4] = 5

所以當打印⇒

arr [0]⇒arr [1]⇒arr [2]⇒arr [3]⇒arr [4]⇒arr [5]

4 0 3 1 5 2

重新排列數組的算法,如果'arr [i]'為'j',則'arr [j]'變為'i'  

1. Traverse the array from 0 to n-1(inclusively).
    1. Do arr [ arr % n ] + = i * n.
2. Then update the value of arr[ i ] =arr[ i ] / n.
3. Print the array.

解釋

給定一個 排列 of 整數。 它擁有的數字在0到n – 1的範圍內。我們將重新排列數字pf數組。 因此,如果數組中的元素為arr [i] = j,則其元素將變為arr [j] = i。 因此,這意味著如果我們在第i個位置具有某個值作為j,則將該值更改為數組的第j個位置。 同樣,我們給定的數組元素在0到n-1的範圍內。 因此,數字不能超過數組的長度。 因此遍歷數組時,可以將任何數字值用作索引並對其執行一些操作,這將是有益的。

也可以看看
解碼方式

因為我們要對數組本身執行一些操作。 我們將選擇每個數組元素並找到 arr [i]%n的整數,其中n是數組的長度。 現在,正如我們前面提到的,數字在0到n-1的範圍內。 因此,當我們用n找出任何數字的模數時。 它不會超過大於數組索引的數字,因為arr [i]%n的模將再次被視為數組索引。 然後我們將其存儲在i * n的乘法中。 將每個取模值更新為數組的索引,並將其與自身求和。

如果要獲取它們,我們只是這樣做來存儲和更新數組中的值。 我們只需要劃分它們。 因為如果將數字乘以x並除以x,數字將保持原樣。 通過將相同的arr [i]除以n來更新arr [i],並將其存儲到arr [i]。 這樣,我們將獲得理想的結果。 這就是如何重新排列數組,如果'arr [i]'為'j',則'arr [j]'變為'i'。

重新排列數組,如果'arr [i]'為'j',則'arr [j]'變為'i'

推薦碼  

用C ++代碼重新排列數組,如果'arr [i]'為'j',則'arr [j]'變為'i'

#include<iostream>

using namespace std;

void rearrangeIndexValue(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[arr[i] % n] += i * n;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] /= n;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,3,5,2,0,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array after modifying :";
    rearrangeIndexValue(arr,n);
    printArray(arr, n);

    return 0;
}
Array after modifying :4 0 3 1 5 2

重新排列數組的Java代碼,如果'arr [i]'為'j',則'arr [j]'變為'i'

class rearrangeArray2
{
    public static void rearrangeIndexValue(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[arr[i] % n] += i * n;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] /= n;
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,3,5,2,0,4};
        int n = arr.length;

        rearrangeIndexValue(arr, n);

        System.out.print("Array after modifying : ");
        printArray(arr, n);
    }
}
Array after modifying : 4 0 3 1 5 2

複雜度分析  

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 即使我們遍歷了數組的元素兩次。 因此,這仍僅算作線性時間複雜度。

也可以看看
計算具有相同偶數和奇數元素的子數組

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 由於我們沒有存儲與每個元素相關的任何內容,並且僅佔用了恆定的空間。 因此,該算法的空間複雜度是恆定的。