# 重新排列数组，使`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 ```