ترتيب عشوائي لصفيف


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Facebook جوجل Microsoft أوراكل
مجموعة مزيج تجزئة

إعطاء مصفوفة أو مجموعة تحتوي على عدد n من العناصر. هنا العناصر فريدة أو لا يوجد تكرار. خلط ملف مجموعة(أو مجموعة) من الأرقام بدون تكرارات.

مثال

// بدء مصفوفة بالمجموعة 2 و 4 و 3 و 1.

int [] nums = {2، 4، 3، 1} ؛

كائن عشوائي = تبديل جديد (أرقام) ؛

// تبديل المصفوفة [2 ، 4 ، 3 ، 1] وإرجاع نتيجتها. أي تبديل لـ [2، 4، 3، 1] يجب أن يتم إرجاعه بشكل متساوٍ ، على سبيل المثال [4، 2، 1، 3] object.shuffle ()؛

// يعيد تعيين المصفوفة إلى تكوينها الأصلي للمصفوفة أي [2 ، 4 ، 3 ، 1].

solution.reset () ؛

يمكننا القيام بذلك باستخدام التعقيد الزمني O (n) باستخدام اثنين من علامات التجزئة.

بنيات البيانات المستخدمة في الترتيب العشوائي للصفيف

الخريطة M (لتخزين القيمة ، زوج الفهرس)

الخريطة K (لتخزين القيمة ، الفهرس المتغير)

المتجه arr لتخزين العناصر الحالية الموجودة في المصفوفة.

فمثلا:

ترتيب عشوائي لصفيف

خوارزمية لوظيفة المنشئ

  1. لكل عنصر موجود في أرقام المصفوفة المحددة:
    1. arr [i] = nums [i]
    2. أدخل زوج قيمة المفتاح (الأعداد [i] ، i) في K.
    3. أدخل زوج قيمة المفتاح (nums [i] ، i) في M.

خوارزمية لإعادة التعيين ()

  1. لكل إدخال موجود في الخريطة M (مكرره):
    1. arr [it.second] = arr [it.first] ، قم بتحديث المتجه بالقيم الأصلية.
  2. العودة آر.

خوارزمية للخلط العشوائي ()

  1. قم بتشغيل حلقة من n إلى 0:
    1. حدد فهرس عشوائي (فهرس) في النطاق (0 ، ن).
    2. خذ العنصر الموجود في الفهرس وقم بتبديله بالعنصر الأخير الموجود في المصفوفة.
    3. قم بتحديث قيم التجزئة لعنصر الفهرس والعنصر الأخير في الخريطة K.
  2. العودة آر.

تطبيق

برنامج C ++ لـ Shuffle an Array

#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 

برنامج JAVA لـ Shuffle an Array

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 

تحليل التعقيد لخلط المصفوفة

تعقيد الوقت

O (n) جميع الوظائف ، أي دالة Constructor ، و shuffle () ، و reset () لأن كل الوظائف تحتاج إلى اجتياز المصفوفة مرة واحدة فقط. لهذا السبب يقودنا إلى التعقيد الزمني الخطي.

تعقيد الفضاء

O (n) ، نحتاج إلى 2 hashmap مساعد بحجم n لتخزين زوج مؤشر القيمة.

مراجع