arr [i]가 i와 같도록 배열 재 배열

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

“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와 같도록 배열을 재배 열하는 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]

복잡성 분석

시간 복잡성

어레이를 순회하고 있었기 때문에 선형 시간 복잡성을 달성했습니다. 의 위에) 어디에 "엔" "arr [i] = i가되도록 배열 재정렬"문제에 대한 배열의 요소 수입니다.

공간 복잡성

알고리즘 자체는 O (1) 상수 공간을 사용하지만 입력이 배열에 저장되기 때문입니다. 우리는 의 위에) 어디에 "엔" 배열의 요소 수입니다.