एरे लीटकोड समाधानमा सफ्फल गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब एप्पल ब्लूमबर्ग गुगल माइक्रोसफ्ट
एरे

एरे लेटकोड समाधानले शफल गर्नुहोस् समस्याले हामीलाई 2n लम्बाइको एर्रे प्रदान गर्दछ। यहाँ 2n जनाउँछ कि array लम्बाई समान छ। हामीलाई त्यसपछि एरे शफल गर्न भनियो। यहाँ फेरबदलको मतलब यो होइन कि हामीले अनियमित रूपमा एर्रे सफाल गर्न आवश्यक छ तर एक खास तरीका देखाईएको छ। यदि दिइएको एर्रेलाई [x1, x2,…, y1, y2,…] को रूपमा प्रतिनिधित्व गर्न सकिन्छ भने फेरबदललाई [x1, y1, x2, y2,…] को रूपमा प्रतिनिधित्व गरिनेछ। त्यसैले समस्या धेरै सिधा अगाडि छ र हामी केहि समाधान गर्न को लागी आशा गर्दैन। हामीलाई केवल आवश्यक अनुक्रम प्राप्त गर्न एलिमेन्ट्स स्व्याप गर्न केहि तरिकाहरू पत्ता लगाउन आवश्यक पर्दछ। त्यहाँ इनपुटमा एक अवरोध पनि छ, इनपुट एलिमेन्टहरू १० ^ than भन्दा कम छन्। तर समाधानमा गहिरो डाइभ गर्नु अघि हामी केही उदाहरणहरूमा लूप लिन्छौं।

एरे लीटकोड समाधानमा सफ्फल गर्नुहोस्

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 (१) स्थानमा कुनै अतिरिक्त ठाउँ बिना समस्या समाधान गर्न। हामीले बाइनरी हेरफेरबाट सहयोग लिनु पर्छ। यो कुनै ट्रिकको रूपमा लाग्न सक्छ किनभने यी एल्गोरिदमहरू प्राय: प्रायः देखिदैन। यसैले यी समस्याहरू तदर्थको कोटिमा आउँछन्। समस्या सुल्झाउने पहिलो चरण भनेको केहि गरी एलिमेन्टहरूलाई पहिलो र दोस्रो आधा दोस्रो भागमा जोड्नु हो। तर यस COMBINE को मतलब के हो? हामी तत्वहरूलाई दोस्रो आधाबाट बाँया बायाँ (बायाँ बाइनरी शिफ्ट) १० बिटहरू बदल्छौं। त्यसोभए हामी पहिलो आधाको एलिमेन्टहरू थप्छौं वा दोस्रो हाफको एलिमेन्टहरू ओआरएल लिन्छौं र पहिलो आधाको एलिमेन्टहरू लिन्छौं। त्यसो भए अब एलिमेन्टहरू जोडिएका छन्।

अब केवल मूल एर्रे पार गर्नुहोस्। हामी लूपको लागि सुरू गर्दछौं जुन प्रत्येक पुनरावृत्तिमा २ चरण बढाउँदछ। प्रत्येक चरणमा हामी एलिमेन्टलाई दोस्रो भागबाट लिन्छौं र एलिमेन्टहरूलाई यी स्थानहरूमा xi, yi प्रतिस्थापन गर्दछौं। हामी पहिलो, एआई र दोस्रो भागमा एलिमेन्टहरू लिन र दोस्रो आधामा २ ^ १०-१ ले पहिलो एलिमेन्ट प्राप्त गर्न सक्छौं। दोस्रो तत्व को रूप मा, हामी सही 2 बिट द्वारा प्रत्येक तत्व बदलाव।

एरे लेटकोड समाधानको लागि सफ्फलको लागि कोड

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 (१), एल्गोरिथ्म एक स्थान एल्गोरिथ्म हो। यसैले ठाउँ जटिलता पनि स्थिर छ।