Массивди иретке келтирүү - эң кичинекей, эң чоң, 2-кичинекей, 2-чоң  


Кыйынчылык деңгээли орто
Көп суралган Amazon Citadel Expedia GE Саламаттыкты сактоо Qualcomm Qualtrics Twilio Yatra
согуштук тизме сорттоо

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

Сизде бүтүндөй массив бар дейли. Массивди ирээтке келтирүү - эң кичинекей, эң чоң, 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 Кийинки орунду эң кичине жана 2мд чоңураак алуу керек, андан кийин аны улантуу керек, 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

Массивди ирээтке келтирүү үчүн Java коду - эң кичинекей, эң чоң, 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 log N) кайда "N" массивдеги элементтердин саны. Убакытты татаалдаштыргандыктан, киргизүүнү иреттедик.

ошондой эле
Ыкчам сорттоо

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

O (N) кайда "N" массивдеги элементтердин саны. Бириктирүү өзү O (N) мейкиндигин алат.