配列をジグザグ形式に変換します


難易度 簡単に
よく聞かれる アクセンチュア Amazon (アマゾン) フォーカイテス Teradataの ゾーメ
配列

問題文

「配列をジグザグ形式に変換する」という問題は、 整数の。 問題ステートメントは、配列内の要素がàのように見えるように、配列をジグザグにソートするように要求します。  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 整数。 私たちの仕事は、配列をジグザグに再配置することです。 'のように、偶数の要素が隣接するXNUMXつの要素よりも大きくなるように条件を設定しました。a <b> c <d> e <f '。 ここで、bとdがXNUMXつの隣接する要素よりも大きく、「a」と「c」がXNUMXつの隣接する要素よりも小さいことがわかります。 私たちの仕事は、与えられた配列をこのように配置することです。 このために、ジグザグに配置されるように、配列をトラバースしながら値を交換します。

XNUMXつとマークされます ブーリアン 値をtrueに設定すると、ループのトラバースが開始され、フラグがtrueかどうかが確認されます。 trueの場合、現在の値が次の値より大きいかどうかを確認します。 次に、これらの値を交換します。 そして、ブール値をfalseにマークします。 値を元に戻す必要があります。trueの場合はfalseに更新し、falseの場合はtrueに更新します。 したがって、すべての代替トラバーサルでは、反復ごとに異なるフラグ値があります。 したがって、これを使用すると、パーツの場合でもパーツの場合でも、パーツのみが実行されます。

値を交換するために、else部分で同じことを行います。 トラバーサル内の配列の現在の値が次の値よりも小さい場合。 そして、トラバーサルの後、更新を行った配列を印刷する必要があります。

配列をジグザグ形式に変換します

 

コード

配列をジグザグ形式に変換する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

配列をジグザグ形式に変換する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) where 「n」 配列内の要素の数です。 配列内の要素をトラバースしたばかりなので。 時間計算量は線形です。

スペースの複雑さ

O(1) 余分なスペースは必要ありません。 余分なスペースを使用していないため、スペースの複雑さは一定です。