ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਨੂੰ ਸ਼ਫਲ ਕਰੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਸੇਬ ਬਲੂਮਬਰਗ ਗੂਗਲ Microsoft ਦੇ
ਅਰੇ

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਦੀ ਸਮੱਸਿਆ ਨੂੰ ਬਦਲਣਾ ਸਾਨੂੰ 2n ਲੰਬਾਈ ਦੀ ਐਰੇ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ. ਇੱਥੇ 2n ਦਰਸਾਉਂਦਾ ਹੈ ਕਿ ਐਰੇ ਲੰਬਾਈ ਬਰਾਬਰ ਹੈ. ਸਾਨੂੰ ਫਿਰ ਐਰੇ ਨੂੰ ਬਦਲਣਾ ਦੱਸਿਆ ਜਾਂਦਾ ਹੈ. ਇੱਥੇ ਸ਼ਫਲਿੰਗ ਦਾ ਇਹ ਮਤਲਬ ਨਹੀਂ ਹੈ ਕਿ ਸਾਨੂੰ ਬੇਤਰਤੀਬੇ ਐਰੇ ਨੂੰ ਸ਼ਫਲ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਪਰ ਇਕ ਖਾਸ ਤਰੀਕਾ ਦਿਖਾਇਆ ਗਿਆ ਹੈ. ਜੇ ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ [x1, x2,…, y1, y2,…] ਦੇ ਰੂਪ ਵਿੱਚ ਦਰਸਾਇਆ ਜਾ ਸਕਦਾ ਹੈ ਤਾਂ ਫੇਰਬਦਲ ਨੂੰ [x1, y1, x2, y2,…] ਵਜੋਂ ਦਰਸਾਇਆ ਜਾਂਦਾ ਹੈ. ਇਸ ਲਈ ਸਮੱਸਿਆ ਬਿਲਕੁਲ ਸਿੱਧਾ ਹੈ ਅਤੇ ਸਾਨੂੰ ਕਿਸੇ ਵੀ ਚੀਜ਼ ਦੇ ਹੱਲ ਦੀ ਉਮੀਦ ਨਹੀਂ ਕਰਦਾ. ਸਾਨੂੰ ਲੋੜੀਂਦਾ ਕ੍ਰਮ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਤੱਤਾਂ ਨੂੰ ਸਵੈਪ ਕਰਨ ਲਈ ਕੁਝ wayੰਗ ਲੱਭਣਾ ਪੈਂਦਾ ਹੈ. ਇੰਪੁੱਟ ਨੂੰ ਲੈ ਕੇ ਵੀ ਇਕ ਰੁਕਾਵਟ ਹੈ, ਇਨਪੁਟ ਐਲੀਮੈਂਟਸ 10 ^ 3 ਤੋਂ ਘੱਟ ਹਨ. ਪਰ ਹੱਲ ਵਿੱਚ ਡੂੰਘੀ ਗੋਤਾਖੋਰੀ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ, ਆਓ ਕੁਝ ਉਦਾਹਰਣਾਂ ਤੇ ਇੱਕ ਲੂਪ ਕਰੀਏ.

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਨੂੰ ਸ਼ਫਲ ਕਰੋ

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

ਵਿਆਖਿਆ: ਅਸੀਂ ਅਸਾਨੀ ਨਾਲ ਤਸਦੀਕ ਕਰਦੇ ਹਾਂ ਕਿ ਆਉਟਪੁਟ ਸਮੱਸਿਆ ਦੇ ਅਨੁਸਾਰ ਲਾਗੂ ਕੀਤੇ ਗਏ ਮਾਪਦੰਡਾਂ ਨੂੰ ਪੂਰਾ ਕਰਦਾ ਹੈ. ਜੇ ਅਸੀਂ ਐਰੇ ਦੇ ਐਲੀਮੈਂਟਸ ਨੂੰ ਐਕਸ 1, ਐਕਸ 2, y3 ਤੱਕ ਨਾਮ ਦੇਣਾ. ਅਸੀਂ ਵੇਖ ਸਕਦੇ ਹਾਂ ਕਿ ਤੱਤ ਹੁਣ [x1, y1, x2, y2, x3, y3] ਫੈਸ਼ਨ ਵਿੱਚ ਵਿਵਸਥਿਤ ਕੀਤੇ ਗਏ ਹਨ.

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਨੂੰ ਸ਼ਫਲ ਕਰਨ ਲਈ ਪਹੁੰਚ

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਦੀ ਸਮੱਸਿਆ ਨੂੰ ਸ਼ੈਫਲ ਕਰਨਾ ਇਕ ਖਾਸ ਤਰੀਕੇ ਨਾਲ ਐਰੇ ਨੂੰ ਸ਼ਫਲ ਕਰਨ ਲਈ ਕਹਿੰਦਾ ਹੈ. ਸ਼ਫਲਿੰਗ ਵਾਲਾ ਫੈਸ਼ਨ ਸਾਨੂੰ ਪਹਿਲੇ ਅੱਧ ਦੇ ਤੱਤ ਦੇ ਵਿਚਕਾਰ ਐਰੇ ਦੇ ਪਿਛਲੇ ਅੱਧੇ ਤੱਤ ਰੱਖਣ ਲਈ ਕਹਿੰਦਾ ਹੈ. ਵਧੇਰੇ ਰਸਮੀ ਤੌਰ ਤੇ, ਇੱਕ ਐਰੇ [x1, x2, x3,…, y1, y2, y3,…] ਨੂੰ [x1, y1, x2, y2, x3, y3,… xn, yn] ਵਾਂਗ ਬਦਲਿਆ ਜਾਣਾ ਹੈ. ਇਸ ਲਈ ਕੋਈ ਵਾਧੂ ਜਗ੍ਹਾ ਦੀ ਸਹਾਇਤਾ ਨਾਲ ਸਮੱਸਿਆ ਨੂੰ ਅਸਾਨੀ ਨਾਲ ਹੱਲ ਕਰ ਸਕਦਾ ਹੈ. ਕਿਉਂਕਿ ਫਿਰ ਅਸੀਂ ਉਸੇ ਹੀ ਲੰਬਾਈ ਦੀ ਇਕ ਨਵੀਂ ਐਰੇ ਬਣਾ ਸਕਦੇ ਹਾਂ ਜਿੰਨੀ ਅਸਲੀ ਹੈ. ਅਤੇ ਦੂਜੇ ਅੱਧ ਤੋਂ ਪਹਿਲੇ ਅੱਧ ਤੋਂ ਤੱਤ ਧੱਕੋ. ਇਸ ਤਰੀਕੇ ਨਾਲ ਅਸੀਂ ਲੋੜੀਂਦੀ ਐਰੇ ਨਾਲ ਖਤਮ ਹੁੰਦੇ ਹਾਂ.

O (1) ਸਪੇਸ ਵਿੱਚ ਬਿਨਾਂ ਕਿਸੇ ਵਾਧੂ ਥਾਂ ਦੇ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ. ਸਾਨੂੰ ਬਾਈਨਰੀ ਹੇਰਾਫੇਰੀ ਤੋਂ ਮਦਦ ਲੈਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਹ ਇੱਕ ਚਾਲ ਵਾਂਗ ਜਾਪਦਾ ਹੈ ਕਿਉਂਕਿ ਇਹ ਐਲਗੋਰਿਦਮ ਬਹੁਤ ਅਕਸਰ ਨਹੀਂ ਦੇਖੇ ਜਾਂਦੇ. ਇਸ ਤਰ੍ਹਾਂ ਇਹ ਸਮੱਸਿਆਵਾਂ ਐਡ-ਹੱਕ ਦੀ ਸ਼੍ਰੇਣੀ ਵਿਚ ਆਉਂਦੀਆਂ ਹਨ. ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਦਾ ਪਹਿਲਾ ਕਦਮ ਹੈ ਕਿਸੇ ਤਰ੍ਹਾਂ ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਤੋਂ ਦੂਜੇ ਅੱਧ ਵਿਚ ਤੱਤ ਜੋੜਨਾ. ਪਰ ਇਸ ਕਮਬਿਨ ਦਾ ਕੀ ਅਰਥ ਹੈ? ਅਸੀਂ ਪਹਿਲਾਂ ਤੱਤ ਨੂੰ ਦੂਜੇ ਅੱਧ ਤੋਂ ਖੱਬੇ (ਖੱਬੇ ਬਾਈਨਰੀ ਸ਼ਿਫਟ) ਤੇ 10 ਬਿੱਟ ਨਾਲ ਤਬਦੀਲ ਕਰਦੇ ਹਾਂ. ਫਿਰ ਜਾਂ ਤਾਂ ਅਸੀਂ ਪਹਿਲੇ ਅੱਧ ਦੇ ਤੱਤ ਜੋੜਦੇ ਹਾਂ ਜਾਂ ਦੂਜੇ ਅੱਧ ਦੇ ਤੱਤ ਨੂੰ ਪਹਿਲੇ ਅੱਧ ਦੇ ਤੱਤ ਨਾਲ ਲੈਂਦੇ ਹਾਂ. ਇਸ ਲਈ ਹੁਣ ਤੱਤ ਇਕੱਠੇ ਹੋ ਗਏ ਹਨ.

ਹੁਣ ਸਿਰਫ ਅਸਲ ਐਰੇ ਤੋਂ ਪਾਰ ਲੰਘੋ. ਅਸੀਂ ਇਕ ਲੂਪ ਲਈ ਅਰੰਭ ਕਰਦੇ ਹਾਂ ਜੋ ਹਰੇਕ ਆਕਰਸ਼ਣ ਵਿਚ 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 ਤੱਤ, ਸਮਾਂ ਗੁੰਝਲਦਾਰ ਅਜੇ ਵੀ ਓ (ਐਨ) ਹੋਣਾ ਬਾਕੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1), ਐਲਗੋਰਿਦਮ ਇੱਕ ਅੰਦਰ ਵਾਲੀ ਐਲਗੋਰਿਦਮ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਨਿਰੰਤਰ ਹੈ.