重新排列数组,使arr [i]等于i


难度级别 易得奖学金
经常问 Accenture 土砖 亚马逊 狂徒 风筝 百会
排列 哈希

“重新排列数组,使arr [i] = i”问题指出,您将获得一个范围从0到n-1的整数数组。 由于数组中可能未包含所有元素,因此-1代替了它们。 问题声明要求以这种方式重新排列数组,如果数组中不存在范围之间的数字,则将其标记为-1并将元素重新排列为arr [i] = i。

使用案列

arr[]={9,4,-1,-1,2,7,8,1,5,-1}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

说明:由于任何 范围内不存在元素 然后,将其替换为-1,并将数组索引替换为数字本身。

重新排列数组以使arr [i]等于i的算法

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

说明

我们得到了一个 排列 of 整数 大小为n。 它将包含o到n-1范围内的数字。 某些 数字可能会丢失 从范围。 我们已要求将arr [i]成为值的所有元素替换为i。 如果数组中没有数字,则应将其替换为-1。 假设我们的范围是0到4,其中数组中只有2和3,其余元素是-1,那么我们必须将2和3放在索引处arr [2] = 2和arr [3] = 3,如果1到0范围内不存在任何数字,则其余地方将标记为-4。

我们给出了一个数组。 我们的主要思想是交换数组的元素以解决“重新排列数组,使arr [i] = i”问题。 我们将遍历数组从0到n-1并检查“ i”的每个值。 如果arr [i]大于0,那么我们可以避免 负数。 还有一个条件适用于该条件,以便在其他部分增加“ i”的值时循环不会无限循环,因此我们还要检查arr [i]也应不等于“ i”。 这样它就可以跳过并继续前进,并检查其他值。

我们只需要交换那些大于0且不等于i的值。 另外,我们在一个范围内的单个循环内交换数组,这就是为什么我们采用arr [i]值数组进行交换的原因。 最后打印出数组的那些值。

重新排列数组,使arr [i] = i

实施

重新排列数组以使arr [i]等于i的C ++程序

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}
-1 1 2 -1 4 5 -1 7 8 9

重新排列数组以使arr [i]等于i的Java程序

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

复杂度分析

时间复杂度

由于我们只是遍历数组,因此实现了线性时间复杂度。 上) 哪里 “N” 是“重新排列数组以使arr [i] = i”问题的数组中的元素数。

空间复杂度

该算法本身占用O(1)恒定空间,但是由于输入存储在数组中。 我们得到 上) 哪里 “N” 是数组中元素的数量。