هڪ آرڊي کي وڪيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪريو گوگل Microsoft جي Oracle
ڪيريو هاش هاشمي

ڏني وئي ترتيب يا سيٽ جنهن ۾ اين عناصر شامل آهن. هتي اهي عنصر منفرد آهن يا نه ته ورجائڻ وارو. uffٽڻ هڪ صف(يا هڪ سيٽ) انگن کان سواءِ انگن جو.

مثال

// سيٽ 2 ، 4 ، 3 ۽ 1 سان گڏ صف ۾ شامل ڪريو.

int [] نيم = {2 ، 4 ، 3 ، 1} ؛

شفل وارو اعتراض = نئون شفل (نون)

// صف کي ختم ڪريو [2، 4، 3، 1] ۽ ان جو نتيجو موٽايو. [2، 4، 3، 1] جي ڪنهن به اجازت نامي جي واپس اچڻ لازمي آهي ، مثال طور [4، 2، 1، 3] object.shuffle ()؛

// صف کي پنهنجي اصلي ترتيب واري ترتيب ڏانهن موٽايو آهي ، يعني ، [2، 4، 3، 1].

حل.سائيٽ () ؛

اسان انهي کي استعمال ڪري سگهون ٿا O (n) وقت جي پيچيدگي کي ٻن هشپس استعمال ڪندي.

شفين ايري لاءِ استعمال ٿيل ڊيٽا جو خاڪو

نقشو ايم (قيمت اسٽور ڪرڻ لاءِ ، انڊيڪس جوئر)

نقشو ڪي (ويليو اسٽور ڪرڻ لاءِ ، بدلجندڙ انڊيڪس)

صف ۾ موجود موجوده عنصرن کي اسٽور ڪرڻ لاءِ ويڪر آر.

مثال طور:

هڪ آرڊي کي وڪيو

تعميراتي فنڪشن لاءِ الگورٿيم

  1. ڏنل عنصر نمبرن ۾ موجود هر عنصر لاءِ:
    1. arr [i] = نمبر [i]
    2. اهم قيمت وارو جوڙو داخل ڪريو (نيون [i] ، i) K.
    3. ايم ويل ۾ ويليوئر جوڙو داخل ڪريو (نمبر (i) ، i)

ريگيوٽريٽ ري سيٽ ڪرڻ لاءِ ()

  1. نقشي ايم ۾ موجود هر داخلا لاءِ (انهي کي ورجايو):
    1. arr [it.second] = arr [اهو پهريون] ، ويڪر کي اصل قدرن سان تازه ڪريو.
  2. واپس آر.

شفل لاءِ الورورٿم ()

  1. n کان 0 تائين لوپ هليو.
    1. حد ۾ بي ترتيب واري انڊيڪس (انڊيڪس) کي منتخب ڪريو (0 ، n).
    2. عنصر تي موجود عنصر کي وٺو ۽ صف ۾ موجود آخري عنصر سان ان کي مٽايو.
    3. نقشي ڪي ۾ انڊيڪس عنصر ۽ آخري عنصر لاءِ هش ويليو کي تازو ڪريو.
  2. واپس آر.

تي عملدرآمد

سي ++ پروگرام شفل آرري لاءِ

#include<bits/stdc++.h>
using namespace std;
class Shuffle {
public:
    vector<int> arr;
    unordered_map<int,int> m;
    unordered_map<int,int> k;
    Shuffle(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            arr.push_back(nums[i]);
            m.insert({nums[i],i});
            k.insert({nums[i],i});
        }
    }
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        for(auto it:m){
            arr[it.second]=it.first;
        }
        return arr;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int n=arr.size();
        while(n){
            int in=rand()%n;
            int index= k[arr[n-1]];
            k[arr[n-1]]=k[arr[in]];
            k[arr[in]]=index;
            swap(arr[in],arr[n-1]);
            n--;
        }
        return arr;
    }
};

int main()
{
    vector<int> nums = {2,3,4,1,5,6};
    Shuffle* obj = new Shuffle(nums);
    cout<<"Original array:\n";
    for(int i=0;i<nums.size();i++){
        cout<<nums[i]<<" ";
    }
    vector<int> _shuffle = obj->shuffle();
    cout<<"\nArray after shuffle:\n";
    for(int i=0;i<_shuffle.size();i++){
        cout<<_shuffle[i]<<" ";
    }
    vector<int> _reset = obj->reset();
    cout<<"\nArray after reset:\n";
    for(int i=0;i<_reset.size();i++){
        cout<<_reset[i]<<" ";
    }
    return 0;
}
Original array:
2 3 4 1 5 6 
Array after shuffle:
2 4 1 5 6 3 
Array after reset:
2 3 4 1 5 6 

جاوا پروگرام شفل هڪ آرڊي لاءِ

import java.util.*;
class Shuffle {
    HashMap<Integer, Integer> m,k;
    int[] arr;

    public Shuffle(int[] nums) {
        m = new HashMap<>();
        k = new HashMap<>();
        int n=nums.length;
        arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=nums[i];
            m.put(nums[i],i);
            k.put(nums[i],i);
        }
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        for(Map.Entry<Integer, Integer> it : m.entrySet()){
            arr[it.getValue()]=it.getKey();
        }
        return arr;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int n=arr.length;
        Random rand = new Random(); 
        while(n>0){
            int in=rand.nextInt(n);
            int index = k.get(arr[n-1]);
            k.put(arr[n-1],k.get(arr[in]));
            k.put(arr[in],index);
            int temp = arr[in];
            arr[in] = arr[n-1];
            arr[n-1] = temp;
            n--;
        }
        return arr;
    }
}
public class Main
{
  public static void main(String[] args) {
      int[] nums = {2,3,4,6};
        Shuffle obj = new Shuffle(nums);
        System.out.print("Original array:\n");
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        int[] _shuffle = obj.shuffle();
        System.out.print("\nArray after shuffle:\n");
        for(int i=0;i<_shuffle.length;i++){
            System.out.print(_shuffle[i]+" ");
        }
        int[] _reset = obj.reset();
        System.out.print("\nArray after reset:\n");
        for(int i=0;i<_reset.length;i++){
            System.out.print(_reset[i]+" ");
        }
  }
}
Original array:
2 3 4 6 1 0 1 0 
Array after shuffle:
4 6 2 3 
Array after reset:
2 3 4 6 

شفل ايري لاء پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ن) سڀ فنڪشن يعني بنايندڙ فنڪشن ، شفل () ، ري سيٽ () جئين سڀني فنڪشن کي صرف هڪ ڀيرو صف جي جڙت جي ضرورت هوندي آهي. ان ڪري اھو اسان کي سڌي وقت جي پيچيدگين ڏانھن وٺي ٿو.

خلائي پيچيدگي

اي (ن) ، اسان کي قيمت انڊيڪس جي جوڙي کي رکڻ لاءِ سائز جي 2 معاون هشپ گهرجن.

حوالا