მასივი გადაიყვანეთ Zig-Zag მოდის რეჟიმში


Რთული ტური Easy
ხშირად ეკითხებიან Accenture Amazon Fourkites Teradata Xome
Array

პრობლემის განცხადება

პრობლემა "მასივი ზიგ-ზაგის მოდად გადაკეთება" აღნიშნავს, რომ თქვენ გეძლევათ - მთელი რიცხვების. პრობლემის დებულება ითხოვს მასივის დალაგებას ზიგ-ზაგის წესით ისე, რომ მასივის ელემენტები გამოიყურებოდეს  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' ნაკლებია ვიდრე მისი ორი მიმდებარე ელემენტი. ჩვენი ამოცანაა მოცემული მასივის ასე დალაგება. ამისათვის ჩვენ ვაპირებთ შეცვალოთ მნიშვნელობები, მასივის გავლისას, ისეთი, რომელიც ზიგზაგის წესით არის მოწყობილი.

ჩვენ მონიშნეთ ერთი ლოგიკური მნიშვნელობა ჭეშმარიტად, მაშინ ჩვენ დავიწყებთ მარყუჟის გადახედვას და გადავამოწმებთ დროშა სიმართლეს, თუ არა. თუ ეს სიმართლეა, ჩვენ შეამოწმებთ მიმდინარე მნიშვნელობას, არის თუ არა ამჟამინდელი მნიშვნელობა უფრო მეტი ვიდრე მისი შემდეგი მნიშვნელობა. შემდეგ ჩვენ ვაპირებთ შევცვალოთ ეს მნიშვნელობები. და ლოგიკური მნიშვნელობები მონიშნეთ false- ით. ჩვენ უბრალოდ უნდა დავაბრუნოთ მისი მნიშვნელობა, თუ ეს სიმართლეა, მაშინ განაახლეთ იგი ცრუზე, თუ მცდარია, განაახლეთ ჭეშმარიტად. ასე რომ, ყველა ალტერნატიული გადაკვეთისას, ყველა გამეორებისთვის, იქნება სხვადასხვა დროშის მნიშვნელობები. ამრიგად, მხოლოდ ნაწილის შესრულება ხდება, თუ ეს არის ნაწილი ან სხვა.

იგივე გავაკეთებთ დანარჩენ ნაწილთანაც, რომ შევცვალოთ მნიშვნელობები. თუ მასივის ამჟამინდელი მნიშვნელობა ტრავერსალში ნაკლებია შემდეგ მნიშვნელობაზე. გავლის შემდეგ, ჩვენ უბრალოდ უნდა დავბეჭდოთ მასივი, რომელშიც განახლებები გავაკეთეთ.

მასივი გადაიყვანეთ 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

ჯავის კოდი მასივის 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც ჩვენ უბრალოდ გადავკვეთეთ მასივის ელემენტებს. დროის სირთულე წრფივია.

სივრცის სირთულე

O (1) რადგან დამატებითი ადგილი არ არის საჭირო. მას შემდეგ, რაც ჩვენ არ გამოვიყენეთ დამატებითი სივრცე, სივრცის სირთულე მუდმივია.