მასივის გადალაგება წესრიგში - ყველაზე პატარა, უდიდესი, მე -2 ყველაზე პატარა, მე -2 უდიდესი


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ციხედ Expedia GE Healthcare Qualcomm Qualtrics Twilio Yatra
Array დახარისხება

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

დავუშვათ, რომ მთელი რიგი გაქვთ. პრობლემა "მასივის გადალაგება მწყობრში - ყველაზე პატარა, უდიდესი, მე -2 ყველაზე პატარა, მე -2 უდიდესი, .." ითხოვს მასივის გადალაგებას ისე, რომ ჯერ მოვიდეს ყველაზე მცირე რიცხვი, შემდეგ კი ყველაზე დიდი, შემდეგ მეორე ყველაზე პატარა და შემდეგ მეორე ყველაზე დიდი და ა.შ.

მაგალითი

arr[] = {1,4,6,2,3,8,9,7}
1 9 2 8 3 7 4 6

განმარტება: ყველაზე მცირე რიცხვია 1, ხოლო ყველაზე დიდი 9, 2nd ყველაზე მცირე, როგორც 2 და 2nd ყველაზე დიდი, როგორც 8, 3rd ყველაზე პატარა არის 3 და 3rd უდიდესი არის 7, მე -4 ყველაზე პატარა არის 3 და მე -4 უდიდესი არის 7. ამრიგად, შედეგი გამოდის ისე განლაგებულია, როგორც ეს პრობლემშია ნათქვამი.

მასივის გადალაგების ალგორითმი - ყველაზე პატარა, ყველაზე დიდი, მე -2 ყველაზე პატარა, სიდიდით მე -2

1. Sort the given array.
2. We have to use a temporary array, so declare one.
3. Set index to 0.
4. Traverse the array from left and from right, with i = 0 and j = n – 1 up the half of the array length.
    1. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
    2. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
5. Update the original array by storing the value of a temporary array to the original array.
6. At last, the original array should be printed.

განმარტება

მასივის გათვალისწინებით რიცხვები. ჩვენ ვთხოვეთ მასივის გადაწყობა ისე, რომ ყველაზე მცირე და ყველაზე დიდი რიცხვი მასივი უნდა მოვიდეს შესაბამისად პირველი და მეორე. შემდეგ 2nd შემდეგ უნდა მოვიდეს ყველაზე მცირე და 2md უდიდესი რიცხვი, შემდეგ კი გავაგრძელოთ ის, 3rd ყველაზე პატარა და 3rd შემდეგი რიგით ყველაზე მეტი უნდა მოვიდეს. ამ თანმიმდევრობით, მასივი უნდა გადავალაგოთ. ჩვენ ვიყენებთ დამატებით მასივს ამ მოთხოვნის შესასრულებლად. დალაგეთ მასივი ისე, რომ ყველა მოდიოდეს შემცირების წესით.

მასივის დახარისხებით, მასივის შიგნით გვაქვს ყველაზე მცირე რიცხვი და მეორე ნახევარში, შესაბამისად. დავუშვათ, რომ გვაქვს რიცხვი 1-დან 10-მდე, მასიურად ინახება მასივი, და თუ დავალაგებთ, 1-დან 5-მდე იქნება პირველ ნახევარში და 6-დან 10-მდე იქნება მეორე ნახევარში.

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

მასივის გადალაგება წესრიგში - ყველაზე პატარა, უდიდესი, მე -2 ყველაზე პატარა, მე -2 უდიდესი

კოდი

C ++ კოდი მასივის გადალაგების მიზნით - ყველაზე პატარა, ყველაზე დიდი, მე -2 ყველაზე პატარა, მე -2 უდიდესი

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeInOrderSL(int arr[], int n)
{
    sort(arr, arr + n);

    int temporaryArray[n];

    int Index = 0;

    for (int i = 0, j = n-1; i <= n / 2 ||j > n / 2; i++, j--)
    {
        temporaryArray[Index] = arr[i];
        Index++;
        temporaryArray[Index] = arr[j];
        Index++;
    }
    for (int i = 0; i < n; i++)
        arr[i] = temporaryArray[i];

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {1,4,6,2,3,8,9,7};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangeInOrderSL(arr, n);

    return 0;
}
1 9 2 8 3 7 4 6

ჯავის კოდი მასივის გადალაგების მიზნით - ყველაზე პატარა, უდიდესი, მე -2 ყველაზე პატარა, მე -2 უდიდესი

import java.util.Arrays;
class rearrangeArraySL
{
    public static void rearrangeInOrderSL(int arr[], int n)
    {
        Arrays.sort(arr);

        int[] temporaryArray = new int[n];

        int Index = 0;

        for (int i = 0, j = n-1; i <= n / 2 || j > n / 2; i++, j--)
        {
            if(Index < n)
            {
                temporaryArray[Index] = arr[i];
                Index++;
            }

            if(Index < n)
            {
                temporaryArray[Index] = arr[j];
                Index++;
            }
        }
        for (int i = 0; i < n; i++)
            arr[i] = temporaryArray[i];
    }
    public static void main(String args[])
    {
        int arr[] = {1,4,6,2,3,8,9,7};
        int n = arr.length;
        rearrangeInOrderSL(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");
    }
}
1 9 2 8 3 7 4 6

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

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

O (N ჟურნალი N) სადაც "N" არის მასივის ელემენტების რაოდენობა. ჩვენ დავალაგეთ შენატანი, რის გამოც გვაქვს ამ დროის სირთულე.

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

O (N) სადაც "N" არის მასივის ელემენტების რაოდენობა. შერწყმის დალაგება თავად იღებს O (N) ადგილს.