Массивыг дахин зохион байгуулах нь arr [i] нь i-тэй тэнцүү байх болно  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accenture Adobe Амазоны Фанатикууд Фуркайт Zoho
Array Хаш

“Arr [i] = i” гэсэн асуудалд танд 0-ээс n-1 хүртэлх бүхэл тоон массивыг өгч байгаа гэсэн массивыг дахин зохион байгуул. Бүх элементүүд массивт байхгүй байж болох тул тэдгээрийн оронд -1 байна. Асуудлын шийдэл нь массивын хооронд тоо байхгүй бол массивыг ийм байдлаар дахин байрлуулж дараа нь -1 гэж тэмдэглээд элементүүдийг arr [i] = i болгож өөрчилнө.

Жишээ нь  

arr[]={9,4,-1,-1,2,7,8,1,5,-1}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

Тайлбар: аль ч оноос хойш элемент хязгаарт байхгүй байна дараа нь үүнийг -1-ээр сольж, массивын индексийг дугаараар нь сольсон болно.

Массивыг дахин зохион байгуулах алгоритм нь arr [i] нь i-тэй тэнцүү байх болно  

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

Тайлбар  

Бидэнд массив of бүхэл тоо хэмжээтэй n. Энэ нь o-n-1 хүртэлх тоонуудыг агуулна. Зарим нь тоо байхгүй байж болно мужаас. Arr [i] -г i болгоно гэсэн бүх элементүүдийг орлуулахыг бид хүссэн. Хэрэв массив дотор дугаар байхгүй бол бид үүнийг -1-ээр солих хэрэгтэй. Бид 0-ээс 4-ийн хооронд хэлбэлзэж байна гэж үзье, үүнд бид зөвхөн 2 ба 3 нь массивт байгаа бөгөөд үлдсэн хэсэг нь -1 элемент байвал бид индекс дээр 2 ба 3-ыг arr [2] = гэж байрлуулах ёстой. 2 ба arr [3] = 3 ба бусад тоонууд 1-ээс 0-ийн хооронд байхгүй бол бусад газруудыг -4 гэж тэмдэглэнэ.

мөн үзнэ үү
Массиваас хамгийн сайн бүтээгдэхүүнтэй хосыг хайж олох

Бид массив өгсөн. Бидний гол санаа бол массивын элементүүдийг хооронд нь сольж “arr [i] = i” массивыг дахин засах. Бид массивыг 0-ээс n-1 хүртэл туулж, "i" -ийн утга тус бүрийг шалгана. Хэрэв arr [i] нь 0-ээс их байвал бид дараахаас зайлсхийх боломжтой болно сөрөг тоо. Мөн өөр хэсэгт 'i' -ийн утгыг нэмэгдүүлж байгаа тул давталт хязгааргүй үргэлжлэх нөхцөлийг тэнд хэрэглэх нөхцөл бас байдаг тул arr [i] нь мөн «i» -тэй тэнцэхгүй байх ёстойг шалгаж байна. Ингэснээр энэ нь алгасаж, цааш хөдөлж, цаашдын утгыг шалгах боломжтой болно.

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

Arr [i] = i гэсэн массивыг дахин байрлуул

Хэрэгжүүлэх  

Массивыг дахин зохион байгуулах C ++ програм нь arr [i] нь i-тэй тэнцүү байна

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}
-1 1 2 -1 4 5 -1 7 8 9

Массивыг дахин засах Java програм нь arr [i] нь i-тэй тэнцүү байх болно

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

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

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

Бид зөвхөн массивыг дайрч өнгөрч байсан тул шугаман хугацааны нарийн төвөгтэй байдалд хүрсэн. O (N) хаана "N" гэдэг нь “arr [i] = i” гэсэн массивыг дахин зохион байгуулахад зориулсан массив дахь элементүүдийн тоо юм.

мөн үзнэ үү
Уулын массив дахь оргил индекс

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

Алгоритм нь өөрөө O (1) тогтмол зай авдаг боловч оролт нь массивт хадгалагддаг тул. Бид авдаг O (N) хаана "N" массив дахь элементүүдийн тоо юм.