Массивыг хамгийн бага, хамгийн том, 2-р хамгийн бага, 2-р томоор дарааллаар нь дахин байрлуул


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Citadel Expedia GE Эрүүл мэндийн Qualcomm Qualtrics Twilio Ятра
Array Ангилах

Асуудлын мэдэгдэл

Танд бүхэл тоон массив байна гэж бодъё. Асуудлыг “Массивыг дарааллаар нь өөрчлөх - хамгийн жижиг, хамгийн том, 2-р хамгийн бага, 2-р том, ..” гэсэн дарааллаар массивыг хамгийн бага тоо дараа нь хамгийн их тоо, дараа нь хоёрдугаарт, дараа нь хоёрдугаарт орж ирэхээр дахин тохируулахыг хүсч байна. хамгийн том гэх мэт.

Жишээ нь

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

Тайлбар: Хамгийн бага тоо нь 1, хамгийн том нь 9, 2 байнаnd хамгийн бага нь 2 ба 2nd хамгийн том нь 8, 3rd хамгийн бага нь 3 ба 3 байнаrd хамгийн том нь 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 хамгийн их тоо тус тус орж ирэх ба дараа нь үргэлжлүүлээрэйrd хамгийн бага ба 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) орон зайг эзэлдэг.