주어진 배열을 최대 최소 형식으로 재정렬

난이도 쉽게
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 자본 하나 시스코 Facebook 구글 모건 스탠리 (Morgan Stanley) 신탁 VM웨어
배열조회수 762

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

문제 정책

“최대 최소 형태로 주어진 배열 재 배열”문제에서 우리는 정렬 된 정렬 N 개의 요소를 포함합니다. 대체 요소가 ith max 및 ih min이되도록 지정된 정렬 된 양의 정수 배열을 재정렬합니다. 요소 재배 열에 대한 더 나은 이해는 아래를 참조하십시오.

Array [0] = 배열의 최대 값, Array [1] = 배열의 최소값, Array [2] = 배열의 두 번째 최대 값, Array [3] = 배열의 두 번째 최소값, Array [4] = 배열의 세 번째 최대 값 …… 등등.

7
1 2 3 4 5 6 7
7 1 6 2 5 3 4

암호알고리즘

  1. 수정 된 배열을 저장할 보조 더미 배열을 만듭니다.
  2. 배열의 코너 인덱스로 낮음과 높음을 초기화합니다.
  3. 대체 최대 및 최소를 복사하려면 변수 X를 저장하고 True를 초기화하십시오.
  4. X = True이면 최대 값을 복사하고 X = False이면 최소값을 복사합니다.
  5. 루프를 실행하여 요소를 보조 배열에 복사합니다. 요소를 새 배열에 복사 한 후 X 값을 반대로합니다.
  6. X가 True이면 끝에서 요소를 복사하고 X가 False이면 뒤로 이동하여 앞쪽에서 요소를 복사하고 앞으로 이동합니다.
  7. 보조 배열을 주어진 배열에 복사합니다.
  8. 배열을 인쇄하면 요소가 재 배열됩니다.

실시

주어진 배열을 최대 최소 형태로 재배 열하는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
 
//function to rearrange the given sorted array in maximum minimum form
void RearrangeMaxMin(int array[], int N)
{
    int temp[N];//auxilary dummy array with all zeroes
    for (int i=0; i<N; i++)
       {
           temp[i] = 0;
       }
    int low=0, high=N-1; // corner indices of the array 
    int X = true; // indication for which element should be copied
    //copying elements into the temp array
    //according to the given condition
    for (int i=0; i<N; i++)
    {
        if(X)
            {
                temp[i] = array[high--];
            }
        else
            {
                temp[i] = array[low++];
            }
        X = !X;
    }
    for (int i=0; i<N; i++)
     {
        array[i] = temp[i];
     }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout << array[i] << " ";
       }
}
// main function
int main()
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "Input array\n";
    PrintArray(array,N);
    RearrangeMaxMin(array,N);
    cout << "\nOutput array\n";
    PrintArray(array,N);
    return 0;
}
Input array
1 2 3 4 5 6 7 8 9 
Output array
9 1 8 2 7 3 6 4 5

주어진 배열을 최대 최소 형식으로 재 배열하기위한 Java 프로그램

import java.util.Scanner;
class sum
{
    //function to rearrange the given sorted array in maximum minimum form
    public static void RearrangeMaxMin(int array[], int N)
    {
        int temp[] = new int [N];//auxilary dummy array with all zeroes
        for (int i=0; i<N; i++)
           {
               temp[i] = 0;
           }
        int low=0, high=N-1; // corner indices of the array 
        int X = 1; // indication for which element should be copied
        //copying elements into the temp array
        //according to the given condition
        for (int i=0; i<N; i++)
        {
            if(X==1)
                {
                    temp[i] = array[high--];
                }
            else
                {
                    temp[i] = array[low++];
                }
            if(X==1)
            {
                X=0;
            }
            else
            {
                X=1;
            }
        }
        for (int i=0; i<N; i++)
         {
            array[i] = temp[i];
         }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Input array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        RearrangeMaxMin(a,n);
        System.out.println("Output array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}
5
5 4 3 2 1
Input array
5 4 3 2 1 
Output array
1 5 2 4 3

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 배열에있는 요소의 수입니다. 여기서 우리는 최대 n 번 실행되는 두 개의 포인터 메서드를 사용합니다. 따라서이 경우 시간 복잡도는 선형이라고 말할 수 있습니다.

공간 복잡성

의 위에) 최대 요소와 최소 요소의 형태로 요소를 저장하기 위해 보조 배열을 사용하기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »