แปลงอาร์เรย์เป็นแบบซิกแซก  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ อเมซอน โฟร์ไคต์ Teradata Xome
แถว

คำชี้แจงปัญหา  

ปัญหา“ แปลงอาร์เรย์เป็นแบบซิกแซก” ระบุว่าคุณจะได้รับไฟล์ - จำนวนเต็ม คำสั่งปัญหาขอให้จัดเรียงอาร์เรย์ในลักษณะซิกแซกเพื่อให้องค์ประกอบในอาร์เรย์มีลักษณะเป็นà  ก <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 จำนวนเต็ม. งานของเราคือการจัดเรียงอาร์เรย์ใหม่ในลักษณะซิกแซก เราได้กำหนดเงื่อนไขว่าองค์ประกอบจำนวนคู่ควรมากกว่าสององค์ประกอบที่อยู่ติดกันในลักษณะของ 'ก <b> c <d> จ <f '. เราจะเห็นได้ที่นี่ว่า b และ d มีค่ามากกว่าสององค์ประกอบที่อยู่ติดกัน 'a' และ 'c' น้อยกว่าองค์ประกอบที่อยู่ติดกันสองตัว งานของเราคือการจัดเรียงอาร์เรย์ที่กำหนดเช่นนี้ สำหรับสิ่งนี้เราจะสลับค่าในขณะที่ข้ามอาร์เรย์ซึ่งจัดเรียงในลักษณะซิกแซก

ดูสิ่งนี้ด้วย
นับขั้นต่ำเพื่อให้ได้อาร์เรย์ที่ต้องการ

เราจะถูกทำเครื่องหมายเป็นหนึ่งเดียว บูลีน ค่าเป็นจริงจากนั้นเราจะเริ่มสำรวจลูปและตรวจสอบว่าแฟล็กนั้นเป็นจริงหรือไม่ หากเป็นจริงเราจะตรวจสอบค่าปัจจุบันว่าค่าปัจจุบันมากกว่าค่าถัดไปหรือไม่ จากนั้นเราจะสลับค่าเหล่านั้น และทำเครื่องหมายค่าบูลีนเป็นเท็จ เราต้องคืนค่าถ้าเป็นจริงจากนั้นอัปเดตเป็นเท็จหากเป็นเท็จให้อัปเดตเป็นจริง ดังนั้นสำหรับการส่งผ่านทางเลือกทุกครั้งสำหรับการวนซ้ำทุกครั้งจะมีค่าแฟล็กที่แตกต่างกัน ด้วยเหตุนี้จึงมีการดำเนินการเพียงบางส่วนไม่ว่าจะบางส่วนหรือบางส่วน

สิ่งเดียวกับที่เราจะทำกับส่วนอื่นเพื่อสลับค่า หากค่าปัจจุบันของอาร์เรย์ในการส่งผ่านมีค่าน้อยกว่าค่าถัดไป และหลังจากการส่งผ่านเราก็ต้องพิมพ์อาร์เรย์ที่เราทำการอัปเดต

แปลงอาร์เรย์เป็นแบบซิกแซกหมุด

 

รหัส  

รหัส 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) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราเพิ่งข้ามผ่านองค์ประกอบในอาร์เรย์ ความซับซ้อนของเวลาเป็นเส้นตรง

ดูสิ่งนี้ด้วย
ผลิตภัณฑ์สูงสุดของลำดับต่อมาที่เพิ่มขึ้น

ความซับซ้อนของอวกาศ

O (1) เนื่องจากไม่จำเป็นต้องมีพื้นที่เพิ่มเติม เนื่องจากเราไม่ได้ใช้พื้นที่พิเศษใด ๆ ความซับซ้อนของพื้นที่จึงคงที่