Массивди Zig-Zag модасына айландыруу


Кыйынчылык деңгээли жеңил
Көп суралган Accenture Amazon Fourkites Терадата Xome
согуштук тизме

Маселени билдирүү

"Массивди 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 болот.

Algorithm

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 to true, анда биз циклди аралап өтүп, желек чын же туура эместигин текшеребиз. Эгер ал чын болсо, анда учурдагы мааниси кийинки маанисинен чоңураак болсо, анда учурдагы маанисин текшеребиз. Анан ошол баалуулуктарды алмаштырганы жатабыз. Логикалык маанилерди жалган деп белгилеңиз. Биз жөн гана анын баасын кайтарышыбыз керек, эгер ал чын болсо, анда аны жалганга, эгер жалган болсо, аны чындыкка жаңыртыш керек. Ошентип, ар бир альтернативдүү өтүү менен, ар бир кайталоо үчүн ар башка желек мааниси болот. Демек, муну менен, бир бөлүгү же башка бөлүгү болсо, бир гана бөлүгү аткарылат.

Дагы бир нерсе, баалуулуктарды алмаштыруу үчүн, башка бөлүгү менен дагы жасайбыз. Эгерде өтмөктөгү массивдин учурдагы мааниси кийинки мааниден аз болсо. Жана өтмөктөн кийин биз жаңыланган массивди басып чыгарышыбыз керек.

Массивди 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) кайда "N" массивдеги элементтердин саны. Биз жаңы эле массивдеги элементтердин үстүнөн өттүк. Убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (1) ашыкча орун талап кылынбагандыктан. Биз ашыкча мейкиндикти колдонбогондуктан, мейкиндиктин татаалдыгы туруктуу.