Verilmiş bir Array qarışdırın

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

"Verilmiş bir Aralığı qarışdırın" problemində bir verdik array tam ədədi. Verilən massivi qarışdıran bir proqram yazın. Yəni serialdakı elementləri təsadüfi qarışdıracaq.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir

Çıxış formatı

N boşluqla ayrılmış tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

• 1 <= n <= 10 ^ 5
• -10 ^ 6 <= a [i] <= 10 ^ 6

misal

5
1 2 3 4 5

1 4 2 5 3

Bu nümunədə çıxış mümkün nəticələrdən yalnız biridir. Bu proqramı təkrar-təkrar çalıştırdığımızda hər dəfə nəticə dəyişəcəkdir.

Alqoritm

Fisher-Yates qarışıq Alqoritmi xətti zaman mürəkkəbliyində işləyir. Buradakı fərziyyə budur ki, bizə sabit vaxtda təsadüfi say yaradan bir rand () funksiyası verilir.
Fikir son elementdən başlamaq, bütün massivdən təsadüfi seçilmiş bir elementlə dəyişdirməkdir (son daxil olmaqla). İndi 0-dan n-2-yə qədər olan massivi nəzərdən keçirin (ölçüsü 1-ə endirilib) və ilk elementi vurana qədər prosesi təkrarlayın.

1. Dizini başdan-başa elementləri bir-bir keçin.

2. 0 <= j <= i olduğu kimi təsadüfi tam ədədi olan j-ni götürün.

3. Arr [j], arr [i] dəyişdirin.

4. Son yenilənmiş array dizisini [] çap edin.

Həyata keçirilməsi

Verilən Array qarışdırmaq üçün C ++ və Java Proqramı

#include <bits/stdc++.h>
using namespace std;

int shuffle(int a[], int n)
{
  srand ( time(NULL) ); //To not get the same output every time we run this program
  for(int i=n-1;i>=0;--i)
  {
    int j = rand()%(i+1);
    swap(a[i],a[j]);
  }
}
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   shuffle(a,n);
   for(int i=0;i<n;i++)
   {
       cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}

import java.util.Random;
import java.util.Scanner;
class sum
{
    static void shuffle(int a[], int n) 
    { 
        Random r = new Random();
        for(int i=n-1;i>=0;i--)
        {
            int j = r.nextInt(i+1); 
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    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();
        }
        shuffle(a,n);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}

4
-10 5 2 183

5 -10 2 183

Verilmiş bir Aralığı qarışdırmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada bütün massivi bir-bir keçirik və hər element üçün elementin cari vəziyyətindən az olan bir rand () dəyəri ilə dəyişdirmə aparırıq.

Kosmik Mürəkkəblik

O (1) çünki burada köməkçi yer yaratmırıq.