배열을 Zig-Zag 방식으로 변환

난이도 쉽게
자주 묻는 질문 Accenture 아마존 포카이트 테라 데이타
배열조회수 96

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

문제 정책

"배열을 Zig-Zag 방식으로 변환"문제는 - 정수 문제 설명은 배열의 요소가 à처럼 보이도록 배열을 지그재그 방식으로 정렬하도록 요청합니다.  a <b> c <d> e <f.

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

설명

5는 1과 2 (인접한 요소)보다 크고, 7은 인접한 두 요소보다 큽니다. 따라서 8도 마찬가지입니다.

암호알고리즘

1. Mark flag is equal to true.
2. Traverse the array from 0 to n-2, where n is the length of the array.
  1. Check if the flag is true
    1. Check if the current element is greater than the next element.
      1. Swap those values.
    2. Else, check if the current element is greater than the next element,
      1. Check if the current element is lesser than the next element.
        1. Swap those values.
3. Flip the value of the flag.

설명

우리는 정렬 of 정수. 우리의 임무는 배열을 지그재그 방식으로 재배 열하는 것입니다. 짝수 요소가 인접한 두 요소보다 커야하는 조건을 'a <b> c <d> e <f '. 여기서 b와 d는 인접한 두 요소보다 크고 'a'와 'c'는 인접한 두 요소보다 작습니다. 우리의 임무는 주어진 배열을 이와 같이 배열하는 것입니다. 이를 위해 우리는 지그재그 방식으로 배열되도록 배열을 순회하면서 값을 교환 할 것입니다.

우리는 하나로 표시됩니다 부울 값을 true로 설정하면 루프 탐색을 시작하고 플래그가 true인지 아닌지 확인합니다. 참이면 현재 값이 다음 값보다 큰지 현재 값을 확인합니다. 그런 다음 해당 값을 교환합니다. 그리고 부울 값을 false로 표시하십시오. 값이 참이면 되 돌린 다음 거짓으로 업데이트하고 거짓이면 참으로 업데이트하면됩니다. 따라서 모든 대체 순회에서 모든 반복에 대해 다른 플래그 값이 있습니다. 그래서 이것으로, 부분이든 부분이든, 부분 만이 실행될 것입니다.

값을 교체하기 위해 else 부분에서도 동일한 작업을 수행합니다. 순회에서 배열의 현재 값이 다음 값보다 작은 경우. 그리고 순회 후에, 우리는 우리가 업데이트 한 배열을 인쇄하기 만하면됩니다.

배열을 Zig-Zag 방식으로 변환

 

암호

배열을 Zig-Zag 방식으로 변환하는 C ++ 코드

#include <iostream>

using namespace std;

void sortZigZag(int arr[], int n)
{
    bool flag = true;

    for (int i=0; i<=n-2; i++)
    {
        if (flag)
        {
            if (arr[i] > arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        else
        {
            if (arr[i] < arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        flag = !flag;
    }
}
int main()
{
    int arr[] = {2,4,5,1,7,6,8};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortZigZag(arr, n);
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}
2 5 1 7 4 8 6

배열을 Zig-Zag 방식으로 변환하는 Java 코드

import java.util.Arrays;

class zigzagArray
{
    public static void sortZigZag(int arr[])
    {
        boolean flag = true;

        int temp =0;

        for (int i=0; i<=arr.length-2; i++)
        {
            if (flag)
            {
                if (arr[i] > arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }

            }
            else
            {
                if (arr[i] < arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            if(flag==true)
                flag=false;
            else
                flag=true;
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,5,1,7,6,8};
        sortZigZag(arr);
        System.out.println(Arrays.toString(arr));
    }
}
[2, 5, 1, 7, 4, 8, 6]

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 배열의 요소를 방금 탐색했기 때문에. 시간 복잡도는 선형입니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 추가 공간을 사용하지 않았기 때문에 공간 복잡성은 일정합니다.

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