# 重新排列數組，使`arr[i] = i` > 原文： [https://www.geeksforgeeks.org/rearrange-array-arri/](https://www.geeksforgeeks.org/rearrange-array-arri/) 給定一個長度為 N 的元素數組，范圍從 0 到`N – 1`。所有元素可能不存在于數組中。 如果不存在`element`，則數組中將存在 -1。 重新排列數組，使`A[i] = i`，如果`i`不存在，則在該位置顯示 -1。 **示例**： ``` Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1} Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9] Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8, 11, 10, 9, 5, 13, 16, 2, 14, 17, 4} Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] ``` **方法**： 1.導航數組。 2.檢查`a[i] = -1`，如果是，則忽略它。 3.如果`a[i] != -1`，請檢查元素`a[i]`是否處于其**正確位置（`i = A[i]`）**。 如果是，則忽略它。 4.如果`a[i] != -1`且元素`a[i]`不在其正確的**位置（`i != A[i]`）**，則將其放置在其正確的位置，但 有兩個條件： * **`A[i]`空出**，意味著`A[i] = -1`，然后將`A[i] = i`放進去。 * 或**`A[i]`未騰空**，表示`A[i] = x`，則`int y = x`放入`A[i] = i`。 現在，我們需要將**和**放置到正確的位置，因此從步驟 3 開始重復。 以下是上述方法的實現： ## C++ ```cpp // CPP program for rearrange an // array such that arr[i] = i. #include <bits/stdc++.h> using namespace std; // Function to rearrange an array // such that arr[i] = i. int fix(int A[], int len) { ????for (int i = 0; i < len; i++)? ????{ ????????if (A[i] != -1 && A[i] != i)? ????????{ ????????????int x = A[i]; ????????????// check if desired place ????????????// is not vacate ????????????while (A[x] != -1 && A[x] != x) ????????????{ ????????????????// store the value from ????????????????// desired place ????????????????int y = A[x]; ????????????????// place the x to its correct ????????????????// position ????????????????A[x] = x; ????????????????// now y will become x, now ????????????????// search the place for x ????????????????x = y; ????????????} ????????????// place the x to its correct ????????????// position ????????????A[x] = x; ????????????// check if while loop hasn't ????????????// set the correct value at A[i] ????????????if (A[i] != i)? ????????????{ ????????????????// if not then put -1 at ????????????????// the vacated place ????????????????A[i] = -1; ????????????} ????????} ????} } // Driver function. int main() { ????int A[] = { -1, -1, 6, 1, 9, ????????????????3, 2, -1, 4, -1 }; ????int len = sizeof(A) / sizeof(A[0]); ????fix(A, len); ????for (int i = 0; i < len; i++) ????????cout << A[i] << " "; } // This code is contributed by Smitha Dinesh Semwal ```