將數組轉換為Zig-Zag時尚


難度級別 容易獎學金
經常問 埃森哲 亞馬遜 風箏 Teradata數據 Xome
排列

問題陳述

問題“將數組轉換為Zig-Zag格式”表明您得到了一個 - 整數問題聲明要求以Z字形方式對數組進行排序,以使數組中的元素看起來像à  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也大於XNUMX。

算法

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”小於其兩個相鄰元素。 我們的任務是像這樣安排給定的數組。 為此,我們將在遍歷數組時交換值,以之字形方式排列它們。

我們將被標記為一個 布爾 如果將value設置為true,則我們將開始遍歷循環,並檢查該標誌是否為true。 如果為true,則如果當前值大於其下一個值,我們將檢查當前值。 然後,我們將交換這些值。 並將布爾值標記為false。 我們只需要還原其值,如果為true,則將其更新為false,如果為false,則將其更新為true。 因此,對於每個替代遍歷,對於每次迭代,都會有不同的標誌值。 因此,無論是零件還是零件,都將僅執行一部分。

我們將對else部分進行相同的操作,以交換值。 如果遍歷中數組的當前值小於下一個值。 遍歷之後,我們只需要打印進行更新的數組即可。

將數組轉換為Zig-Zag時尚

 

推薦碼

用C ++代碼將數組轉換為Zig-Zag方式

#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代碼將數組轉換為Zig-Zag時尚

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) 哪裡 “ n” 是數組中元素的數量。 由於我們剛剛遍歷了數組中的元素。 時間複雜度是線性的。

空間複雜度

O(1) 因為不需要額外的空間。 由於我們沒有使用任何多餘的空間,因此空間複雜度是恆定的。