가장 작은 것, 가장 큰 것, 두 번째로 작은 것, 두 번째로 큰 순서대로 배열 재정렬

난이도 중급
자주 묻는 질문 아마존 성 Expedia GE 헬스 케어 퀄컴 Qualtrics Twilio 야 트라
배열 정렬조회수 29
링크드 인버퍼레딧텀블러

문제 정책

정수 배열이 있다고 가정합니다. “가장 작은 것, 큰 것, 두 번째로 작은 것, 두 번째로 큰 것, ..”순서대로 배열을 재정렬하는 문제는 가장 작은 숫자가 먼저 나온 다음 가장 큰 숫자, 두 번째로 작은 숫자, 두 번째 순서로 배열을 재정렬하도록 요청합니다. 가장 큰 등등.

예

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

설명 : 가장 작은 숫자는 1이고 가장 큰 숫자는 9, 2입니다.nd 2와 2로 가장 작음nd 최대 8, 3rd 가장 작은 것은 3과 3입니다.rd 가장 큰 것은 7, 네 번째로 작은 것은 4이고 네 번째로 큰 것은 3입니다. 따라서 결과 출력은 문제에서 말한 것과 같은 방식으로 배열됩니다.

배열을 순서대로 재정렬하는 알고리즘 – 최소, 최대, 두 번째로 작은, 두 번째로 큰

1. Sort the given array.
2. We have to use a temporary array, so declare one.
3. Set index to 0.
4. Traverse the array from left and from right, with i = 0 and j = n – 1 up the half of the array length.
    1. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
    2. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
5. Update the original array by storing the value of a temporary array to the original array.
6. At last, the original array should be printed.

설명

주어진 배열 정수. 우리는 가장 적은 수와 가장 많은 수의 배열을 재 배열하도록 요청했습니다. 정렬 각각 2 위와 XNUMX 위가되어야합니다. 그런 다음 XNUMXnd 가장 작은 숫자와 2md 가장 큰 숫자가 각각 다음에 와야합니다.rd 최소 및 3rd 가장 큰 숫자가 그 다음으로 와야합니다. 이 순서에서 우리는 배열을 재 배열해야합니다. 이 요구 사항을 충족하기 위해 추가 어레이를 사용할 것입니다. 모든 것이 감소하지 않는 순서로 오도록 주어진 배열을 정렬하십시오.

배열을 정렬하면 배열 내에서 각각 절반에 가장 작은 숫자와 다른 절반에 가장 큰 숫자가 있습니다. 배열에 무작위로 저장된 1에서 10까지의 숫자가 있다고 가정하고 정렬하면 1에서 5까지가 전반에, 6에서 10이 후반에 있다고 가정합니다.

마찬가지로 여기에서 이제 왼쪽에서 순회하여 생성 한 배열에 값을 저장할 수 있습니다. 왼쪽부터 시작하므로 가장 작은 요소 만 있으므로 해당 요소를 임시 배열에 삽입 할 수 있습니다. 따라서 첫 번째 위치에는 가장 작은 요소 만 있습니다. 이제 오른쪽에서 이동합니다. 배열이 정렬되어 가장 큰 요소가 있어야하므로 이제 해당 요소를 임시 배열에 넣습니다. 우리의 첫 번째 가장 작은 요소와 가장 큰 요소가 완료되었습니다. 이제 이전에했던 것처럼 더 나아가 왼쪽 다음 요소에서 임시 배열로 이동 한 다음 오른쪽에서 두 번째로 큰 요소를 선택하여 배열에 저장해야합니다. , 우리는 원하는 결과를 얻을 수 있습니다. 이제 단순히 그 배열을 인쇄하십시오.

가장 작은 것, 가장 큰 것, 두 번째로 작은 것, 두 번째로 큰 순서대로 배열 재정렬핀

암호

배열을 순서대로 재정렬하는 C ++ 코드 – 최소, 최대, 두 번째로 작은, 두 번째로 큰

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeInOrderSL(int arr[], int n)
{
    sort(arr, arr + n);

    int temporaryArray[n];

    int Index = 0;

    for (int i = 0, j = n-1; i <= n / 2 ||j > n / 2; i++, j--)
    {
        temporaryArray[Index] = arr[i];
        Index++;
        temporaryArray[Index] = arr[j];
        Index++;
    }
    for (int i = 0; i < n; i++)
        arr[i] = temporaryArray[i];

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {1,4,6,2,3,8,9,7};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangeInOrderSL(arr, n);

    return 0;
}

1 9 2 8 3 7 4 6

배열을 순서대로 재배 열하는 Java 코드 – 최소, 최대, 두 번째로 작은, 두 번째로 큰

import java.util.Arrays;
class rearrangeArraySL
{
    public static void rearrangeInOrderSL(int arr[], int n)
    {
        Arrays.sort(arr);

        int[] temporaryArray = new int[n];

        int Index = 0;

        for (int i = 0, j = n-1; i <= n / 2 || j > n / 2; i++, j--)
        {
            if(Index < n)
            {
                temporaryArray[Index] = arr[i];
                Index++;
            }

            if(Index < n)
            {
                temporaryArray[Index] = arr[j];
                Index++;
            }
        }
        for (int i = 0; i < n; i++)
            arr[i] = temporaryArray[i];
    }
    public static void main(String args[])
    {
        int arr[] = {1,4,6,2,3,8,9,7};
        int n = arr.length;
        rearrangeInOrderSL(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");
    }
}

1 9 2 8 3 7 4 6

복잡성 분석

시간 복잡성

O (N log N) 어디에 "엔" 배열의 요소 수입니다. 이 시간 복잡성으로 인해 입력을 정렬했습니다.

공간 복잡성

의 위에) 어디에 "엔" 배열의 요소 수입니다. 병합 정렬 그 자체는 O (N) 공간을 차지합니다.

링크드 인버퍼레딧텀블러
Translate »