Mündəricat
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.
