Verilən İndekslərdən istifadə edərək Array yenidən düzəldin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
GeyimBaxılıb 345

Problem bəyanat

Verilən indekslər problemindən istifadə edən yazıcı massivində eyni ölçülü, ikincisi olan iki giriş massivi verdik array indeks massividir, verilmiş indeks massivinə görə eyni massivdəki elementləri yenidən sıralamalıyıq.

misal

Input
sıra: [4, 2, 1, 3]
indeks: [3, 1, 0, 2]

Buraxılış
sıra: [1, 2, 3, 4]
indeks: [0, 1, 2, 3]
Burada verilən indeks massivi [3, 1, 0, 2],
Buna görə də, sıra [3] = 4, massiv [1] = 2, sıra [0] = 1, sıra [2] = 3.
Çıxış belə olacaq: [1, 2, 3, 4]

Input
sıra: [9, 5, 3, 7, 11, 1]
indeks: [4, 2, 1, 0, 3, 5]

Buraxılış
sıra: [7, 3, 5, 11, 8, 9, 1]
indeks: [0, 1, 2, 3, 4, 5]

Yanaşma 1

Alqoritm

1 Adım: İki giriş massivi [] və indeks [] götürən və indeks massivinə əsaslanan yenidən sifariş verən bir funksiya yaradın.

2 Adım: Funksiyada

a) Verilən massivlərlə eyni ölçüdə köməkçi bir sıra yaradın.
b) Verilən massivdən keçin və indeksə əsasən tempdə elementləri düzgün vəziyyətə gətirin. temp [index [i]] = array [i]
c) Bu temp massivini verilmiş bir sıra kimi kopyalayın və indekslər əsasında indeks massivini dəyişdirin.

3 Adım: verilmiş giriş massivlərinə bu funksiyanı çağırın və massivləri çap edin.

Həyata keçirilməsi

Üçün C ++ Proqramı Verilən İndekslərdən istifadə edərək Array yenidən düzəldin

#include <bits/stdc++.h>
using namespace std;
 
//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
    int temp[N];//auxilary array    
    //array[i] should present at (index[i]) index
    for (int i=0; i<N; i++)
    {
        temp[index[i]] = array[i];
    }
    for (int i=0; i<N; i++)
    { 
       array[i] = temp[i];
       index[i] = i;
    }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout << array[i] << " ";
       }
}
//Main function
int main()
{
    int array[] = {50, 40, 70, 60, 90};
    int index[] = {3,  0,  4,  1,  2};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "Input array: \n";
    PrintArray(array,N);
    cout << "\nInput index array: \n";
    PrintArray(index,N);
    //Reordering by using function 
    Reorder(array,index,N);
 
    cout << "\nOutput array: \n";
    PrintArray(array,N);
    cout << "\nOutput index array: \n";
    PrintArray(index,N);
    return 0;
}
Input array: 
50 40 70 60 90 
Input index array: 
3 0 4 1 2 
Output array: 
40 60 90 50 70 
Output index array: 
0 1 2 3 4

Verilən İndekslərdən istifadə edərək Array Yenidən Sifariş üçün Java Proqramı

import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
    //Function for reoreder elements based on index array
    public static void Reorder(int array[], int index[], int N)
    {
        int temp[] = new int [N];//auxilary array    
        //array[i] should present at (index[i]) index
        for (int i=0; i<N; i++)
        {
            temp[index[i]] = array[i];
        }
        for (int i=0; i<N; i++)
        { 
           array[i] = temp[i];
           index[i] = i;
        }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
           for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        System.out.println("Input array:");
        PrintArray(a,n);
        System.out.println("\nInput index array: ");
        PrintArray(index,n);
        //Reordering by using function 
        Reorder(a,index,n);
        System.out.println("\nOutput array: ");
        PrintArray(a,n);
        System.out.println("\nOutput index array: ");
        PrintArray(index,n);
    }
}
5
9 3 5 1 7
0 4 2 3 1
Input array:
9 3 5 1 7 
Input index array: 
0 4 2 3 1 
Output array: 
9 7 5 1 3 
Output index array: 
0 1 2 3 4

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (n) burada n massivin ölçüsüdür. Burada serialı keçirik və elementi köməkçi massivdə düzgün vəziyyətdə yerləşdiririk.

Kosmik Mürəkkəblik

O (n) elementləri düzgün vəziyyətdə saxlamaq üçün köməkçi bir sıra istifadə etdiyimiz yer.

Yanaşma 2

Alqoritm

1 Adım: Bir yaradın funksiyası verilmiş massivləri və indeks dizisinə əsasən yenidən sifarişləri götürən.

2 Adım: Əgər indeks [i] = i olarsa, giriş massivindəki bütün elementlər üçün vəziyyəti belə dəyişməyimiz lazım deyil.
a) Düzgün mövqe massivində saxlama dəyərləri [i] saxta dəyişənlərə yerləşdirilməlidir.
b) Dizini [i] mövqeyinə qoyun və indeks dəyərini yeniləyin. (array [index [i]] = array [i])
c) Köhnə dəyərləri cari vəziyyətə köçürün. array [i] = oldElementvalue və yeniləmə indeksi.

3 Adım: yenidən sıralamaq üçün bu funksiya giriş massivlərini çağırın.

Həyata keçirilməsi

Verilən İndekslərdən istifadə edərək Dizini Yenidən Sıralamaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
 
//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
    for(int i=0; i<N; i++)
    {
        while (index[i] != i)
        {
            //storing correct position values
            int  oldIndexValue = index[index[i]];
            char oldElementValue   = array[index[i]];
            array[index[i]] = array[i];
            index[index[i]] = index[i];
            index[i] = oldIndexValue;
            array[i]   = oldElementValue;
        }
    }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout << array[i] << " ";
       }
}
//Main Function
int main()
{
   int array[] = {50, 40, 70, 60, 90};
    int index[] = {3,  0,  4,  1,  2};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "Input array: \n";
    PrintArray(array,N);
    cout << "\nInput index array: \n";
    PrintArray(index,N);
    //Reordering by using function 
    Reorder(array,index,N);
 
    cout << "\nOutput array: \n";
    PrintArray(array,N);
    cout << "\nOutput index array: \n";
    PrintArray(index,N);
    return 0;
}
Input array: 
50 40 70 60 90 
Input index array: 
3 0 4 1 2 
Output array: 
40 60 90 50 70 
Output index array: 
0 1 2 3 4

Verilən İndekslərdən istifadə edərək Array Yenidən Sifariş üçün Java Proqramı

import java.util.Scanner;
class sum
{
    //Function for reoreder elements based on index array
    public static void Reorder(int array[], int index[], int N)
    {
        for(int i=0; i<N; i++)
        {
            while (index[i] != i)
            {
                //storing correct position values
                int  oldIndexValue = index[index[i]];
                int oldElementValue   = array[index[i]];
                array[index[i]] = array[i];
                index[index[i]] = index[i];
                index[i] = oldIndexValue;
                array[i]   = oldElementValue;
            }
        }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
           for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        System.out.println("Input array:");
        PrintArray(a,n);
        System.out.println("\nInput index array: ");
        PrintArray(index,n);
        //Reordering by using function 
        Reorder(a,index,n);
        System.out.println("\nOutput array: ");
        PrintArray(a,n);
        System.out.println("\nOutput index array: ");
        PrintArray(index,n);
    }
}
5
1 2 3 4 5
4 3 2 1 0
Input array:
1 2 3 4 5 
Input index array: 
4 3 2 1 0 
Output array: 
5 4 3 2 1 
Output index array: 
0 1 2 3 4

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (n) burada n massivin ölçüsüdür. Burada da zamanın mürəkkəbliyinin xətti olduğuna görə bir dəfə massivi keçirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

References

Translate »