მასივის გადალაგება ისე, რომ ინდექსის ელემენტებიც კი მცირეა და უცნაური ინდექსის ელემენტებიც მეტია


Რთული ტური Easy
ხშირად ეკითხებიან ავალარა ეპიკური სისტემები ფურკიტები რობლოქსი Tesla
Array

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

თქვენ მიანიჭეთ მასივი of რიცხვები. პრობლემა "მასივის გადალაგება ისე, რომ ინდექსის ელემენტებიც უფრო მცირეა და უცნაური ინდექსის ელემენტები უფრო დიდია" ითხოვს მასივის გადალაგებას ისე, რომ ლუდის ინდექსის ელემენტები უნდა იყოს უფრო მცირე, ვიდრე უცვლელი ინდექსის ელემენტები შეცვლილი მასივიდან.

მაგალითი

arr[]={ 2,5,7,1,3,4 }
2 7 1 5 3 4

განმარტება: 2 არის ლუდის ინდექსის პოზიციაზე (0 ინდექსი), ამიტომ ის უფრო მცირეა, ვიდრე შემდეგი კენტი ინდექსირებული ელემენტი, 1 ნაკლებია 5-ზე, რომელიც კენტი ინდექსირებულ ელემენტზეა.

მასივის გადალაგების ალგორითმი ისეთი, რომ ინდექსირებული ელემენტებიც კი უფრო მცირეა, ვიდრე უცნაური ინდექსირებული

1. Traverse the array from 0 to n-1(less than the length of the array).
2. Check if the index is even and the next element is smaller than the current element then swap both of the numbers.
3. Check if the index is odd and the next element is greater than the current element, then swap both of the numbers.
4. Print the array.

განმარტება

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

მასივის გადაკვეთა 0-დან ნაკლები n-1-ზე ნაკლები, სადაც n არის მასივის სიგრძე. გადაადგილამდე აიღეთ ერთი ნაკლები ვიდრე n-1, რადგან მასში შედარებას ვაპირებთ შემდეგ ელემენტთან. ამიტომ ჩვენ უნდა დავტოვოთ ეს ადგილი შედარებისთვის, თუ ეს შეცდომით მოხდა. თუ n -ზე ნაკლებს გამოვყოფთ, ის მოხვდება ინდექსში, რომელიც მასივში არ არსებობს. სწორედ ამიტომ, ჩვენ მივიღეთ 0 – ზე ნაკლები n - 1 ტრასა.

ჩვენ გადავხედავთ მასივს და გადავამოწმებთ "i" - ის თითოეულ მნიშვნელობას, თუ ეს არის ლუწი ან კენტი, თუ ის არის ლუწი და ასევე array [i] მეტია შემდეგ ელემენტზე. ეს ნიშნავს მომდევნო ელემენტის პოზიციას, რადგან i ნამდვილად უცნაურია და ეს უცნაური პოზიციონირებული ელემენტი ნაკლებია, ვიდრე ლუწი პოზიციონირებული ელემენტი. ჩვენ ვაპირებთ ელემენტების შეცვლას arr [i] არის ამჟამინდელი ლუწი ელემენტი და arr [i + 1] არის შემდეგი უცნაური პოზიციონირებული ელემენტი.

ახლა ერთდროულად ვამოწმებთ არის თუ არა "i" - ის მნიშვნელობა უცნაური და ასევე, თუ ამ ინდექსში არსებული ელემენტი უფრო მცირეა, ვიდრე წინა ელემენტი, მაშინ ჩვენ ვაპირებთ შეცვალოთ მასივის მნიშვნელობები. ყველა შესაძლო მნიშვნელობის შეცვლის შემდეგ, ასე ჩამოყალიბებული მასივი იქნება საბოლოო და სასურველი გამომავალი.

მასივის გადალაგება ისე, რომ ინდექსის ელემენტებიც კი მცირეა და უცნაური ინდექსის ელემენტებიც მეტია

კოდი

C ++ კოდი მასივის გადალაგებისათვის ისე, რომ ინდექსირებული ელემენტებიც კი უფრო მცირეა, ვიდრე უცნაური ინდექსირებული

#include <iostream>
using namespace std;

void evenOddComparison (int* arr, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (i % 2 == 0 && arr[i] > arr[i + 1])
            swap(arr[i], arr[i + 1]);

        if (i % 2 != 0 && arr[i] < arr[i + 1])
            swap(arr[i], arr[i + 1]);
    }
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";

    cout << endl;
}

int main()
{
    int arr[] = {  2,5,7,1,3,4  };
    int n = sizeof(arr) / sizeof(arr[0]);

    evenOddComparison (arr, n);

    printArray(arr, n);

    return 0;
}
2 7 1 5 3 4

ჯავის კოდი მასივის გადალაგებისათვის ისე, რომ ინდექსირებული ელემენტებიც კი უფრო მცირეა, ვიდრე უცნაური ინდექსირებული

class rearrangeArray
{
    public static void evenOddComparison(int arr[], int n)
    {

        int temp;
        for (int i = 0; i < n - 1; i++)
        {
            if (i % 2 == 0 && arr[i] > arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
            if (i % 2 != 0 && arr[i] < arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
    public static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,5,7,1,3,4 };
        int n = arr.length;

        evenOddComparison (arr, n);

        printArray(arr, n);
    }
}
2 7 1 5 3 4

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ჩვენ უბრალოდ გადავკვეთეთ მასივი და შევცვალეთ ელემენტები, ამიტომ დროის სირთულე ხაზოვანია.

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

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