अ‍ॅरे लीटकोड सोल्यूशन शफल करा


अडचण पातळी सोपे
वारंवार विचारले अडोब सफरचंद ब्लूमबर्ग Google मायक्रोसॉफ्ट
अरे

अ‍ॅरे लीटकोड सोल्यूशन शफल करा ही समस्या आम्हाला 2n लांबीची अ‍ॅरे प्रदान करते. येथे 2 एन संदर्भित की अॅरे लांबी सम आहे. त्यानंतर अ‍ॅरेमध्ये फेरबदल करण्यास सांगितले जाते. येथे फेरबदल करण्याचा अर्थ असा नाही की आम्हाला यादृच्छिकपणे अ‍ॅरे शफल करणे आवश्यक आहे परंतु एक विशिष्ट मार्ग दर्शविला गेला आहे. जर दिलेला अ‍ॅरे [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]

स्पष्टीकरणः आम्ही सहजपणे सत्यापित करतो की समस्येमध्ये लागू केल्याप्रमाणे आउटपुट आवश्यक निकषांची पूर्तता करतो. जर आपण अ‍ॅरेच्या घटकांना y1 पर्यंत x2, x3 अशी नावे दिली तर. आपण पाहू शकता की घटक आता [x1, y1, x2, y2, x3, y3] फॅशनमध्ये व्यवस्थित केलेले आहेत.

अ‍ॅरे लीटकोड सोल्यूशनसाठी शफल करा

अ‍ॅरे लीफकोड सोल्यूशन शफल करा ही समस्या विशिष्ट प्रकारे अ‍ॅरे शफल करण्यास सांगते. फेरबदल करणारी फॅशन आम्हाला आधीच्या अर्ध्या घटकांमधील अ‍ॅरेचे शेवटचे अर्धे घटक ठेवण्यास सांगते. अधिक औपचारिकरित्या, अ‍ॅरे [x1, x2, x3,…, y1, y2, y3,…] [x1, y1, x2, y2, x3, y3,… xn, yn] म्हणून बदलले जाणे आवश्यक आहे. म्हणून अतिरिक्त जागेच्या मदतीने समस्या सहज सोडवता येते. कारण मग आपण मूळच्या समान लांबीचा नवीन अ‍ॅरे सहजपणे तयार करू शकतो. आणि पहिल्या अर्ध्यापासून नंतर दुसर्‍या अर्ध्यापासून घटकांना ढकलून द्या. अशा प्रकारे आम्ही आवश्यक अ‍ॅरेसह संपतो.

ओ (1) जागेत कोणत्याही अतिरिक्त जागेशिवाय समस्येचे निराकरण करण्यासाठी. आम्हाला बायनरी हेराफेरीसाठी मदत घेणे आवश्यक आहे. हे युक्तीसारखे वाटू शकते कारण हे अल्गोरिदम बरेचदा पाहिले जात नाहीत. अशा प्रकारे या समस्या तदर्थ श्रेणीच्या खाली येतात. समस्येचे निराकरण करण्याची पहिली पायरी म्हणजे पहिल्या आणि दुसर्‍या अर्ध्यापासून दुसर्‍या अर्ध्या भागामध्ये काही प्रमाणात घटक एकत्र करणे. परंतु या COMBINE चा अर्थ काय आहे? आम्ही प्रथम घटकांना दुसर्‍या अर्ध्यापासून डावीकडे (डाव्या बायनरी शिफ्ट) 10 बिट्सने शिफ्ट करतो. तर एकतर आम्ही पहिल्या अर्ध्यातील घटक जोडू किंवा दुसर्‍या अर्ध्याच्या घटकांचा ओआर घेतो किंवा पहिल्या अर्ध्याच्या घटकांसह. आता घटक एकत्र केले आहेत.

आता फक्त मूळ अ‍ॅरेवर जा. आम्ही एक लूप सुरू करतो ज्या प्रत्येक पुनरावृत्तीच्या 2 चरणांमध्ये वाढ करते. प्रत्येक चरणात आम्ही दुसर्‍या अर्ध्या भागातून एखादा घटक निवडतो आणि या ठिकाणी घटकांना क्ष, यी सह बदलतो. प्रथम घटक मिळविण्यासाठी आम्ही दुस half्या सहामाहीत 2 आणि 10-1 सह घटकांच्या प्रथम आणि त्याद्वारे xi, yi मिळवू शकतो. दुसर्‍या घटकाविषयी, आम्ही प्रत्येक घटकास 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 घटक, वेळ जटिलता अद्याप ओ (एन) असणे बाकी आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1), अल्गोरिदम ही एक जागा-अल्गोरिदम आहे. अशा प्रकारे जागेची जटिलता देखील स्थिर आहे.