მასივის გადალაგება ისეთი, რომ arr [i] ტოლია i


Რთული ტური Easy
ხშირად ეკითხებიან Accenture Adobe Amazon ფანატიკა Fourkites Zoho
Array Hash

”მასივის გადალაგება ისე, რომ 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" არის მასივის ელემენტების რაოდენობა.