Массивыг жигд индекс элементүүд нь жижиг, сондгой индекс элементүүд их байхаар дахин байрлуул


Хэцүү байдлын түвшин Easy
Байнга асуудаг Авалара Эпик системүүд Фуркайт Roblox Tesla
Array

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

Та өгсөн массив of бүхэл тоо. "Шулуун индекс элементүүд нь жижиг, сондгой индексийн элементүүд нь их байхаар массивыг дахин зохион байгуул" гэсэн асуудал массивыг тэгш индекс элементүүд нь өөрчлөгдсөн массив дахь сондгой индекс элементүүдээс бага байхаар дахин байрлуулахыг хүсдэг.

Жишээ нь

arr[]={ 2,5,7,1,3,4 }
2 7 1 5 3 4

Тайлбар: 2 нь тэгш индексийн байрлалд (0 индекс) байгаа тул дараагийн сондгой индексжүүлсэн элементээс бага, 1 нь сондгой индекслэгдсэн элемент дээр байгаа 5-аас бага байна.

Массивыг индексжүүлсэн элементүүд нь сондгой индексжүүлсэн хэмжээнээс бага байхаар цэгцлэх алгоритм

1. Traverse the array from 0 to n-1(less than the length of the array).
2. Check if the index is even and the next element is smaller than the current element then swap both of the numbers.
3. Check if the index is odd and the next element is greater than the current element, then swap both of the numbers.
4. Print the array.

Тайлбар

N урттай массив өгөгдсөн болно. Массивыг тэгш индексийн элементүүд сондгой индекслэгдсэн элементүүдээс бага байхаар өөрчлөн зохион байгуулахыг биднээс хүсч байна. Хэрэв нөхцөл хангагдаагүй бол элементүүдийг солих замаар бид үүнийг хийх болно. Нэгдүгээрт, бид түүний төрлийг тэгш эсвэл сондгойгоор нь шалгаж дараа нь өөрчлөх хэрэгтэй массив.

Массивыг 0-ээс n-1-ээс бага дайран өнгөрөх ба n нь массивын урт юм. Хэрэв массивт байгаа бол дараагийн элементтэй харьцуулах тул n-1-ээс бага гүйлгэх хэрэгтэй. Тиймээс бид алдаанаас болж харьцуулахын тулд тэр газрыг орхих хэрэгтэй. Хэрэв бид n-ээс бага давталт хийвэл массивт байхгүй индексийг цохино. Тийм ч учраас бид 0-ээс n - 1-ээс бага гүйлт авсан.

Бид массивыг дайран өнгөрч, 'i' -ийн утга тус бүр тэгш эсвэл сондгой байгаа эсэхийг шалгаж, массив [i] нь дараагийн элементээс их байна. Энэ нь i-ийн сондгой тул дараагийн элементийн байрлалыг илэрхийлнэ, сондгой байрлалтай элемент нь тэгш байрлалтай элементээс бага байна. Arr [i] нь одоогийн тэгш элемент бөгөөд arr [i + 1] нь дараагийн сондгой байрлалтай элемент тул бид элементүүдийг хооронд нь солих болно.

Одоо бид 'i' -ийн утга сондгой байгаа эсэхийг, мөн энэ индекс дээрх элемент өмнөх элементээс бага байгаа эсэхийг шалгаад дараа нь массив дахь утгуудыг солих болно. Бүх боломжит утгуудыг сольсны дараа үүссэн массив нь эцсийн бөгөөд хүссэн гаралт болно.

Массивыг жигд индекс элементүүд нь жижиг, сондгой индекс элементүүд их байхаар дахин байрлуул

код

Массивыг дахин индексжүүлсэн элементүүд нь сондгой индексжүүлсэн хэмжээнээс бага байхаар цэгцлэх C ++ код

#include <iostream>
using namespace std;

void evenOddComparison (int* arr, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (i % 2 == 0 && arr[i] > arr[i + 1])
            swap(arr[i], arr[i + 1]);

        if (i % 2 != 0 && arr[i] < arr[i + 1])
            swap(arr[i], arr[i + 1]);
    }
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";

    cout << endl;
}

int main()
{
    int arr[] = {  2,5,7,1,3,4  };
    int n = sizeof(arr) / sizeof(arr[0]);

    evenOddComparison (arr, n);

    printArray(arr, n);

    return 0;
}
2 7 1 5 3 4

Индексжүүлсэн элементүүд нь сондгой индексжүүлсэн хэмжээнээс бага байхаар массивыг дахин байрлуулах Java код

class rearrangeArray
{
    public static void evenOddComparison(int arr[], int n)
    {

        int temp;
        for (int i = 0; i < n - 1; i++)
        {
            if (i % 2 == 0 && arr[i] > arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
            if (i % 2 != 0 && arr[i] < arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
    public static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,5,7,1,3,4 };
        int n = arr.length;

        evenOddComparison (arr, n);

        printArray(arr, n);
    }
}
2 7 1 5 3 4

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Бид дөнгөж массивыг дайрч, элементүүдийг хооронд нь сольсон тул цаг хугацааны нарийн төвөгтэй байдал нь шугаман байна.

Сансрын нарийн төвөгтэй байдал

O (1) Учир нь бид тогтмол орон зайг ашиглаж байсан боловч програмыг бүхэлд нь O (n) зай эзэлдэг.