ارے لیٹکوڈ حل کو تبدیل کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایپل بلومبرگ گوگل مائیکروسافٹ
لڑی

ایری لیٹکوڈ حل کی شفل مسئلہ ہمیں لمبائی 2n کی ایک صف فراہم کرتا ہے۔ یہاں 2n سے مراد ہے کہ صف لمبائی بھی ہے۔ اس کے بعد ہمیں صف کو تبدیل کرنے کے لئے کہا جاتا ہے۔ یہاں شفلنگ کا مطلب یہ نہیں ہے کہ ہمیں تصادفی طور پر صف کو تبدیل کرنا ہوگا لیکن ایک خاص طریقہ دکھایا گیا ہے۔ اگر دیئے گئے صف کی نمائندگی [x1، x2،…، y1، y2،…] کے طور پر کی جاسکتی ہے تو پھر بدلتے ہوئے [x1، y1، x2، y2،…] کی نمائندگی کی جاتی ہے۔ تو مسئلہ بالکل سیدھا ہے اور ہم سے کسی بھی چیز کو حل کرنے کی توقع نہیں کرتا ہے۔ ہمیں مطلوبہ ترتیب حاصل کرنے کے لئے عناصر کو بدلنے کے لئے کچھ راستہ تلاش کرنے کی ضرورت ہے۔ ان پٹ پر بھی ایک رکاوٹ ہے ، ان پٹ عنصر 10 ^ 3 سے کم ہیں۔ لیکن حل میں گہرا غوطہ لگانے سے پہلے ، آئیے کچھ مثالوں پر ایک چکر لگائیں۔

ارے لیٹکوڈ حل کو تبدیل کریں

nums = [2,5,1,3,4,7], n = 3
[2,3,5,4,1,7]

وضاحت: ہم آسانی سے تصدیق کرتے ہیں کہ آؤٹ پٹ مسئلے میں عائد کردہ مطلوبہ معیار کو پورا کرتا ہے۔ اگر ہم سرنی کے عناصر کو نامزد کرنے جیسے x1 ، x2 ، y3 تک تفویض کرتے ہیں۔ ہم دیکھ سکتے ہیں کہ عناصر کو اب [x1، y1، x2، y2، x3، y3] فیشن میں ترتیب دیا گیا ہے۔

شفل ارے لیٹکوڈ حل کیلئے اپروچ

ایری لیٹ کوڈ حل کی اشکال مسئلہ ایک خاص انداز میں سرنی میں شفل کرنے کو کہتے ہیں۔ بدلتے ہوئے فیشن ہمیں پہلے ہاف کے عناصر کے درمیان صف کے آخری نصف عنصر رکھنے کے لئے کہتے ہیں۔ مزید رسمی طور پر ، ایک صف [x1، x2، x3،…، y1، y2، y3،…] کو [x1، y1، x2، y2، x3، y3،… xn، yn] کے طور پر تبدیل کیا جانا ہے۔ لہذا کوئی اضافی جگہ کی مدد سے مسئلہ آسانی سے حل کرسکتا ہے۔ کیونکہ اس کے بعد ہم اسی لمبائی کی ایک نئی صف تشکیل دے سکتے ہیں جتنا کہ اصلی سے زیادہ ہے۔ اور پہلے نصف سے دوسرے نصف حصے سے عناصر کو دبائیں۔ اس طرح ہم مطلوبہ صف کے ساتھ ختم ہوجاتے ہیں۔

کسی اضافی جگہ کے بغیر مسئلہ حل کرنے کے لئے جو O (1) جگہ میں ہے۔ ہمیں بائنری ہیرا پھیری سے مدد لینے کی ضرورت ہے۔ یہ ایک چال کی طرح معلوم ہوسکتی ہے کیونکہ یہ الگورتھم اکثر اکثر نہیں دیکھے جاتے ہیں۔ اس طرح یہ مسائل ایڈہاک کے زمرے میں آتے ہیں۔ مسئلے کو حل کرنے کا پہلا قدم کسی طرح پہلے اور دوسرے نصف حصے سے دوسرے نصف حصے میں عناصر کو جوڑنا ہے۔ لیکن اس COMBINE کا کیا مطلب ہے؟ ہم پہلے عناصر کو دوسرے نصف حصے سے بائیں (بائیں بائنری شفٹ) میں 10 بٹس سے منتقل کرتے ہیں۔ پھر یا تو ہم پہلے نصف کے عنصر شامل کرتے ہیں یا ہم پہلے نصف کے عناصر کے ساتھ دوسرے حصے کے عناصر میں سے OR لے جاتے ہیں۔ تو اب عناصر مل گئے ہیں۔

اب صرف اصل صف سے آگے بڑھیں۔ ہم ایک لوپ شروع کرتے ہیں جو ہر تکرار میں 2 قدموں میں اضافہ کرتا ہے۔ ہر مرحلے میں ہم دوسرے نصف حصے سے ایک عنصر چنتے ہیں اور ان مقامات پر موجود عناصر کو xi ، yi سے تبدیل کرتے ہیں۔ ہم پہلے عنصر کو حاصل کرنے کے لئے دوسرے حصے میں 2 ^ 10-1 کے ساتھ دوسرے اور نصف حصے میں عناصر کو حاصل کرکے XI ، yi حاصل کرسکتے ہیں۔ جہاں تک دوسرے عنصر کی بات ہے تو ، ہم ہر عنصر کو 10 بٹس سے شفٹ کرتے ہیں۔

ارے لیٹ کوڈ حل کے لئے کوڈ

C ++ کوڈ

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

vector<int> shuffle(vector<int>& nums, int n) {
    for(int i=n;i<2*n;i++){
        nums[i] = nums[i]<<10;
        nums[i] |= nums[i-n];
    }
    int z = n;
    for(int i=0;i<2*n;i+=2){
        nums[i] = nums[z] & 1023;
        nums[i+1] = nums[z++] >> 10;
    }
    return nums;
}

int main() {
    vector<int> input = {2,5,1,3,4,7};
    int n = 3;
    vector<int> output = shuffle(input, n);
    for(auto x: output)
        cout<<x<<" ";
}
2 3 5 4 1 7

جاوا کوڈ

import java.util.*;
import java.io.*;

class Main {
    private static int[] shuffle(int[] nums, int n) {
        for(int i=n;i<2*n;i++){
            nums[i] = nums[i]<<10;
            nums[i] |= nums[i-n];
        }
        int z = n;
        for(int i=0;i<2*n;i+=2){
            nums[i] = nums[z] & 1023;
            nums[i+1] = nums[z++] >> 10;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] input = {2,5,1,3,4,7};
        int n = 3;
        int[] output = shuffle(input, n);
        for(int i=0;i<2*n;i++)
            System.out.print(output[i]+" ");
    }
}
2 3 5 4 1 7

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، چونکہ ہم صف کے ہر عنصر کو عبور کرتے ہیں۔ اگرچہ ہمارے ساتھ فراہم کی جاتی ہے 2n عناصر ، وقت کی پیچیدگی ابھی بھی O (N) باقی ہے۔

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

O (1) ، الگورتھم ایک جگہ الگورتھم ہے۔ اس طرح جگہ کی پیچیدگی بھی مستقل ہے۔