추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞습니다.

난이도 중급
자주 묻는 질문 어도비 벽돌 드 쇼 Expedia 광신자 과연 알레그로
배열 분열과 정복 재귀조회수 28

문제 정책

당신은 주어진 정렬 of 정수. "추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞기"문제는 배열의 모든 숫자를 섞어서 (x0, x1, x2, x3, y0, y1, y2, y3)는 이러한 방식으로 x0, y0, x1, y1, x2, y2, x3, y3 등과 같이 셔플됩니다.

arr[]={1, 3, 5, 7, 2, 4, 6, 8}
1, 2, 3, 4, 5, 6, 7, 8

설명

처음 세 숫자에서 비교하면 x0, x1, x2와 같고 다음 세 숫자는 y0, y1, y2와 같고 x0, y0, x1, y1, x2, y2에 정렬됩니다.

추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞습니다.

추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞는 알고리즘

1. Find out the middle index of the array.
2. While middleIndex greater than 0, set count and swappingIndex to middleIndex.
  1. While the count is greater than 0, do the following steps.
    1. Swap the values at swappingIndex and swappingIndex +1(value next to swappingIndex).
    2. Increase the value of swapping index by 1.
  2. Decrease the value of middleIndex by 1.
3. Print the array.

설명

우리는 정렬 of 정수.  그런 다음 특히 주어진 방식으로 모든 정수 값을 섞도록 요청받습니다. 어레이의 절반 만 순회합니다. 그리고 알고리즘에 따라 오는 모든 값을 교체합니다. 먼저 배열이 null이 아니어야하는지 확인합니다. 또한 배열의 길이는 균등해야합니다. 그렇기 때문에 배열 길이가 이상하지 않아야한다는 조건을 확인합니다. 위에서 언급 한 조건 중 하나라도 거짓이면 출력을 생성하지 않습니다.

배열의 중간 인덱스를 찾은 다음 해당 인덱스의 값과 다음 인덱스 값을 확인하고 간단히 교체합니다. 이를 위해 중첩 된 while 루프 첫 번째 while 루프에서. 그런 다음 현재 인덱스에서 0으로 트래버스하고 중간 인덱스의 값을 계속 감소시킵니다. 내부 내부 while 루프, 현재 인덱스와 동일한 값을 swappingIndex에 저장하고 swappingIndex 값과 다음 값을 가져 와서 스왑합니다. 두 번째 스왑의 경우 swappingIndex 값을 늘리고 현재 swappingIndex 및 다음 인덱스 값에 대해 스왑을 수행합니다.

다음 순회를 위해 중간 인덱스의 값을 줄입니다. 배열의 전면에서 값을 가져올 수 있도록합니다. 마찬가지로 count와 swappingIndex는 배열의 이전 값을 탐색하기 위해 줄인 중간 Index 값의 값과 동일합니다. 우리가 수행 한 모든 스와핑 후에, 우리는 그 배열을 인쇄 할 것이고 모든 숫자는 주어진 방식으로 섞일 것입니다.

암호

추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞는 C ++ 코드

#include<iostream>
using namespace std;

void shuffleInt(int arr[], int n)
{
    if (arr == NULL || n % 2 == 1)
        return;

    int middleIndex = (n - 1) / 2;

    while (middleIndex > 0)
    {
        int countIndex = middleIndex, swappingIndex = middleIndex;

        while (countIndex -- > 0)
        {
            int temp = arr[swappingIndex + 1];
            arr[swappingIndex + 1] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            swappingIndex++;
        }
        middleIndex--;
    }
}
int main()
{
    int arr[] = {1, 9, 25, 4, 16, 36};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffleInt(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i]<<" ";
}
1 4 9 16 25 36

추가 공간을 사용하지 않고 2n 정수를 a1-b1-a2-b2-a3-b3-.. bn으로 섞는 Java 코드

class Shuffle2nIntegers
{
    public static void shuffleInt(int[] arr)
    {

        if (arr == null || arr.length % 2 == 1)
            return;

        int middleIndex = (arr.length - 1) / 2;


        while (middleIndex > 0)
        {
            int countIndex = middleIndex, swappingIndex = middleIndex;

            while (countIndex -- > 0)
            {
                int temp = arr[swappingIndex + 1];
                arr[swappingIndex + 1] = arr[swappingIndex];
                arr[swappingIndex] = temp;
                swappingIndex++;
            }
            middleIndex--;
        }
    }

    public static void main(String[] args)
    {
        int arr[] = {1, 9, 25, 4, 16, 36};
        shuffleInt(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print( arr[i]+" ");
        System.out.println();
    }
}
1 4 9 16 25 36

복잡성 분석

시간 복잡성

O (n ^ 2) 어디에 "엔" 배열의 요소 수입니다. 매번 middleIndex를 0 씩 감소시킵니다. 그러나 내부 루프는 middleIndex 횟수만큼 실행됩니다. 외부 루프가 i = 1에서 n까지 실행되는 간단한 두 개의 중첩 루프로 간주 할 수 있습니다. 내부 루프는 i + XNUMX에서. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (1), 알고리즘은 내부 알고리즘이기 때문입니다. 이것이 수행되고있는 모든 작업이 초기 배열 요소를 대체하는 것입니다. 그리고 새로운 어레이는 만들어지지 않습니다.

Translate »