Преуредување на низата по редослед - најмал, најголем, 2-ри најмал, 2-ри по големина


Ниво на тешкотија Медиум
Често прашувано во Амазон Цитаделата Expedia ГЕ здравство Квалком 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. Така, резултантниот излез е подреден на ист начин како што е кажано во проблемот.

Алгоритам за преуредување на низата по редослед - најмал, најголем, 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мд најголемиот број треба да следат, соодветно, потоа продолжувајќи го, 3-отrd најмал и 3rd најголемиот број треба да дојде следно по ред. Во оваа низа, треба да ја преуредиме низата. Beе користиме дополнителна низа за да го исполниме ова барање. Подреди ја дадената низа така што секој доаѓа по редослед на не-опаѓачки начин.

Со сортирање на низата, имаме најмал број во една половина и најголем број во друга половина во рамките на низата, соодветно. Да претпоставиме дека имаме број од 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 log N) каде „Н“ е бројот на елементи во низата. Го сортиравме влезот поради кој ја имаме оваа сложеност во времето.

Комплексноста на просторот

НА) каде „Н“ е бројот на елементи во низата. Спојување на сортирање самото зафаќа простор О (N).