Перастаўце масіў па парадку - найменшы, самы вялікі, 2-і па памеры, 2-і па велічыні


Узровень складанасці серада
Часта пытаюцца ў амазонка Citadel Expedia GE Healthcare Qualcomm Qualtrics Twilio яйкі
масіў сартаванне

Пастаноўка праблемы

Дапусцім, у вас ёсць цэлалікавы масіў. Задача «Пераставіць масіў па парадку - найменшы, найбольшы, 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 найменшая і найбольшая колькасць павінны прыйсці наступнай адпаведна, потым працягваючы яе, 2rd самы маленькі і 3rd найбольшая колькасць павінна ісці па парадку. У гэтай паслядоўнасці мы павінны пераставіць масіў. Для выканання гэтага патрабавання мы будзем выкарыстоўваць дадатковы масіў. Сартаваць дадзены масіў так, каб кожны прыходзіў у парадку змяншэння.

Сартуючы масіў, мы маем найменшы лік у адной палове і найбольшы лік у другой палове ў масіве адпаведна. Дапусцім, у нас ёсць лік ад 1 да 10, выпадкова захаваны ў масіве, і калі адсартаваць іх, то ад 1 да 5 будзе ў першай палове і ад 6 да 10 будзе ў другой палове.

Падобным чынам тут, зараз мы можам пераходзіць злева і захоўваць значэнні ў створаным намі масіве. Паколькі мы пачынаем злева, будзе толькі самы маленькі элемент, таму мы можам ўставіць гэты элемент у часовы масіў. Такім чынам, на першай пазіцыі ёсць толькі самы маленькі элемент. Цяпер рухайцеся справа, бо масіў адсартаваны так, што павінен быць самы вялікі элемент, таму зараз мы змяшчаем гэты элемент у часовы масіў. Наш першы найменшы і найбуйнейшы завершаны, цяпер рухаемся далей, як і раней, мы павінны перайсці з левага наступнага элемента і захаваць яго ў часовы масіў, а затым з правага боку выбраць другі па велічыні элемент і захаваць яго ў масіў, такім чынам , мы можам дасягнуць патрэбнага выніку. Цяпер проста надрукуйце гэты масіў.

Перастаўце масіў па парадку - найменшы, самы вялікі, 2-і па памеры, 2-і па велічыні

код

Код C ++ для перастаноўкі масіва па парадку - найменшы, найбольшы, другі па памеры, другі па велічыні

#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 для перастаноўкі масіва па парадку - найменшы, найбольшы, другі па памеры, другі па велічыні

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) прастору.