Verilən İndekslərə görə Bir Arrayı yenidən düzəldin

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

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bir giriş massivi və array indekslər, verilmiş indekslərə görə bir sıra yenidən sıralayın. Burada elementləri verilmiş indeks seriyasına uyğun olaraq indekslərə görə düzəltməliyik.

misal

Giriş: arr [] = [23,24,25] və verilən indekslər indeksdir [] = [1,0,2]

23 İndeks 1-ə köçürülməlidir. 24 İndeks 0-a, 25 İndeks 2-də olmalıdır.

Çıxış: arr [] = [24,23,25]

Yuxarıdakı nümunədə, çıxış dizisi indeks 23-də 1, indeks 24-da 0, indeks 25-də 2 olacaqdır.

Yanaşma 1

Dizinin sonuna qədər hər elementi seçin
indeks [i] i-yə bərabər deyil
a. arr [i] və arr [index [i]] elementlərini dəyişdirin
b. index [i], index [index [i]] olan indeksləri dəyişdirin

Verilən İndekslərə görə Bir Array Yenidən Sıralaması üçün İcra

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  int index[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  for(int i=0;i<N;i++)
  {
      cin>>index[i];
  }
  for(int i=0; i<N;i++)
  while(index[i] != i) //keep looping till index[i] is not equal to actual index
  {
     swap(arr[i],arr[index[i]]); //swap both the elements
     swap(index[i],index[index[i]]);  //swap both the indices
  }  
  for(int i=0;i<N;i++)
  cout<<arr[i] <<" ";
  return 0;
}

Java Proqramı

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        for(int i=0; i<n;i++)
        {
            while(index[i] != i) //keep looping till index[i] is not equal to actual index
            {
                a[i]=a[i]+a[index[i]]-(a[index[i]]=a[i]);
                index[i]=index[i]+index[index[i]]-(index[index[i]]=index[i]);
            }
        }  
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}
6
13 53 12 7 3 1
0 5 3 2 4 1
13 1 7 12 3 53

Verilən İndekslərə görə Bir Array Yenidən Sıralamaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n) burada n verilən massivin ölçüsüdür. Burada dizinin dəyərini indeks dizisini istifadə edərək istənilən indeksdə dəyişdiririk. Burada ən çox addım atırıq.

Köməkçi yer

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

Yanaşma 2

Bu yanaşmada bir sıra götürürük və indeks dizisini istifadə edərək elementləri lazımi yerdə saxlayırıq.

Alqoritm

  1. Son nəticəni saxlamaq üçün köməkçi bir sıra yaratmaq.
  2. Dizinin sonunda çatdıqda təkrarlayın.
    1. O indeksə gedərək elementləri indeksə uyğun olaraq köməkçi massivə yerləşdirin
    yəni köməkçi sıra [indeks [i]] = arr [i]

Verilən İndekslərə görə Bir Array Yenidən Sıralaması üçün İcra

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  int index[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  for(int i=0;i<N;i++)
  {
      cin>>index[i];
  }
  int final[N];//create an auxiliary array to store the final result
  for(int i=0; i<N;i++)
    final[index[i]]  = arr[i]; //place the elements according to index by going to that index
    
  for(int i=0;i<N;i++)
    cout<<final[i] <<" ";
  return 0;
}

Java Proqramı

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        int ans[] = new int [n];//create an auxiliary array to store the final result
        for(int i=0; i<n;i++)
          ans[index[i]]  = a[i]; //place the elements according to index by going to that index
        for(int i=0;i<n;i++)
        {
            System.out.print(ans[i]+" ");
        }
        System.out.println();
    }
}
3
23 24 25
1 0 2
24 23 25

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) burada n verilən massivin ölçüsüdür. Budur biz keçmək massivi başdan sona və elementləri yeni massivdə saxlayın.

Köməkçi yer

O (n) çünki elementləri indeksə uyğun olaraq saxlamaq üçün başqa bir sıra istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »