آريري ليٽ ڪوڊ حل کي شراف ڪريو  


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايڊوب ايپل Bloomberg گوگل Microsoft جي
algorithms ڪيريو ڪوڊنگ انٽرويو انٽرويو جي تياري ليٽ ڪوڊ LeetCodeSolutions

مسئلو شي کي ترتيب ڏيو ارري ليٽ ڪوڊ حل اسان کي 2n جي ڊيگهه سان مهيا ڪري ٿو. هتي 2n ظاهر ڪري ٿو صف ڊيگهه اڃا آهي. اسان کي چيو ويو آهي ته ترتيب کي toهليو. هتي شفٽنگ ڪرڻ جو مطلب اهو ناهي ته اسان کي صف کي بي ترتيب سان شفٽ ڪرڻ جي ضرورت آهي پر هڪ خاص رستو ڏيکاريو ويو آهي. جيڪڏهن ڏنل صف ڏيکاري سگهجي ٿي [x1، x2،…، y1، y2،…] پوءِ شفلنگ کي ظاھر ڪيو ويو آھي [x1، y1، x2، y2،…]. تنهن ڪري مسئلو سڌو سڌو آهي ۽ اسان کان ڪجھ به حل ڪرڻ جي توقع ناهي. اسان کي لازمي طور تي عنصر ڳولهڻ جي لاءِ گهربل طريقو ڳولڻ جي لاءِ گهربل آهي. ان پٽ مٿان هڪ رڪاوٽ به آهي ، انپٽ عناصر 10 ^ 3 کان گهٽ آهن. پر حل ۾ اندر وڃڻ کان پهرين ، اچو ته ڪجھ مثالن تي هڪ loopار وٺون.

آريري ليٽ ڪوڊ حل کي شراف ڪريوپن

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

وضاحت: اسان آساني سان تصديق ڪريون ٿا ته محصول گهربل معيار کي پورو ڪري ٿو جئين مسئلو ۾ لاڳو ٿيل. جيڪڏهن اسان صف بندي جي عنصرن کي y1 تائين x2 ، x3 ، نالو ڏيڻ تفويض ڪريون ٿا. اسان ڏسي سگهون ٿا ته عنصر هاڻي ترتيب ڏنل آهن [x1 ، y1 ، x2 ، y2 ، x3 ، y3] فيشن ۾.

شفل ارري ليٽ ڪوڊ حل لاءِ رستو  

مسئلو آهي ارري ليٽ ڪوڊ حل کي صف کي مخصوص انداز ۾ leهلائڻ لاءِ چوندو آهي. fashionرندڙ فيشن اسان کان پڇي ٿو ته پهرين اڌ جي عناصر کي پهرين اڌ جي عناصر جي وچ ۾ رکجي. وڌيڪ رسمي طور ، هڪ صف [x1، x2، x3،…، y1، y2، y3،…] کي شفٽ ڪيو وڃي [x1، y1، x2، y2، x3، y3،… xn، yn]. تنهنڪري هڪ آساني سان اضافي جڳهه جي مدد سان مسئلو حل ڪري سگهي ٿو. ڇو ته پوءِ اسان انهي کي ئي اصل ۾ هڪ ئي ڊگري جي نئين سر ٺاهي سگهنداسين. ۽ عناصر پهرين ٽئين کان پوءِ ٻئي اڌ تائين. انهي طريقي سان اسان گهربل ترتيب سان ختم ڪيو.

پڻ ڏسو
گھڻائي واري اسرنگس ليٽ ڪوڊ حل

مسئلي کي حل ڪرڻ کان سواءِ ڪنھن اضافي جاءِ جو O (1) خلا ۾ آھي. اسان کي بائنري ميراپوليشن کان مدد وٺڻ جي ضرورت آهي. اهو شايد هڪ چال وانگر لڳي ٿو ڇاڪاڻ ته اهي الگورتھم گهڻو ڪري نه ڏٺا ويا آهن. اهڙي طرح اهي مسئلا ايڊہاک جي ڪيٽيگري ۾ اچي ويا. سڀ کان پهرين مسئلي کي حل ڪرڻ ڪنهن نه ڪنهن طريقي سان عنصر کي پاڻ ۾ ملائي ٻئي حصي کان ۽ ٻيو اڌ حصو ٻئي نصف تائين. پر انهي مجموعي جو ڇا مطلب آهي؟ اسان پهريون ڀيرو عنصر کي ٻئي اڌ کان کاٻي طرف (بائیں بائنري شفٽ) 10 بٽس طرف منتقل ڪندا آهيون. پوءِ يا ته اسان پهرين اڌ جي عنصرن کي شامل ڪريون ٿا يا پهرين سيڪنڊ جي عناصر سان OR کي وٺون ٿا. تنهن ڪري هاڻي عنصر گڏيل آهن.

هاڻي صرف اصلي صف تي گهراءِ. اسان لوپ لاءِ شروع ڪريون ٿا جيڪو هر ورثي ۾ 2 قدم وڌائيندو آهي. اسان هر قدم ۾ هڪ ٻيو اڌ ٻئي کان هڪ عنصر چونڊون ٿا ۽ انهن جڳهن تي عناصر کي مٽائڻ جي ڪري xi ، yi. اسان پهرين عنصر حاصل ڪرڻ لاءِ 2 ^ 10-1 سان سيڪنڊ اڌ ۾ عنصرن مان ۽ ايڪس کي حاصل ڪري سگهون ٿا. ٻئي عنصر جي طور تي ، اسان هر عنصر کي صحيح طور تي 10 بٽس طرف منتقل ڪيو ٿا.

ايري ليٽ ڪوڊ حل لاءِ شفل لاءِ ڪوڊ  

سي ++ ڪوڊ

#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

پيچيدگي تجزيي  

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

اي (اين) ، جئين اسان صف جي هر عنصر کي پار ڪيو. جيتوڻيڪ اسان سان مهيا ڪيل آهن 2n عنصرن ، وقت جي پيچيدگي اڃا تائين O (N) رهي ٿي.

پڻ ڏسو
گهٽ ۾ گهٽ مڪمل فرق Leetcode حل

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

اي (1) ، الگورتھم ھڪڙو جڳھھ الگورتھم آھي. ان ڪري خلاءَ جي پيچيدگي پڻ مستقل آهي.

1