അറേ ലീറ്റ്കോഡ് പരിഹാരം ഷഫിൾ ചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആപ്പിൾ ബ്ലൂംബർഗ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ

അറേ ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഷഫിൾ ചെയ്യുന്ന പ്രശ്നം ഞങ്ങൾക്ക് 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]

വിശദീകരണം: പ്രശ്‌നത്തിൽ ചുമത്തിയ ആവശ്യമായ മാനദണ്ഡങ്ങൾ output ട്ട്‌പുട്ട് തൃപ്തിപ്പെടുത്തുന്നുവെന്ന് ഞങ്ങൾ എളുപ്പത്തിൽ പരിശോധിക്കുന്നു. അറേയിലെ ഘടകങ്ങൾക്ക് y1 വരെ x2, x3 പോലുള്ള നാമകരണം നൽകുകയാണെങ്കിൽ. ഘടകങ്ങൾ ഇപ്പോൾ [x1, y1, x2, y2, x3, y3] രീതിയിൽ ക്രമീകരിച്ചിരിക്കുന്നതായി നമുക്ക് കാണാം.

അറേ ലീറ്റ്കോഡ് പരിഹാരം ഷഫിൾ ചെയ്യുന്നതിനുള്ള സമീപനം

ഒരു പ്രത്യേക രീതിയിൽ അറേ ഷഫിൾ ചെയ്യാൻ അറേ ലീറ്റ്കോഡ് പരിഹാരം ആവശ്യപ്പെടുന്ന പ്രശ്നം. ആദ്യ പകുതിയിലെ ഘടകങ്ങൾക്കിടയിൽ അറേയുടെ അവസാന പകുതി ഘടകങ്ങൾ സ്ഥാപിക്കാൻ ഷഫിംഗ് ഫാഷൻ ആവശ്യപ്പെടുന്നു. കൂടുതൽ ly പചാരികമായി, ഒരു ശ്രേണി [x1, x2, x3,…, y1, y2, y3,…] [x1, y1, x2, y2, x3, y3,… xn, yn] ആയി മാറ്റണം. അതിനാൽ അധിക സ്ഥലത്തിന്റെ സഹായത്തോടെ ഒരാൾക്ക് എളുപ്പത്തിൽ പ്രശ്നം പരിഹരിക്കാൻ കഴിയും. കാരണം അപ്പോൾ നമുക്ക് ഒറിജിനലിന്റെ അതേ നീളത്തിൽ ഒരു പുതിയ ശ്രേണി സൃഷ്ടിക്കാൻ കഴിയും. ആദ്യ പകുതി മുതൽ രണ്ടാം പകുതി വരെ ഘടകങ്ങൾ തള്ളുക. ഇതുവഴി ആവശ്യമായ അറേയിൽ ഞങ്ങൾ അവസാനിക്കും.

O (1) സ്ഥലത്തുള്ള അധിക ഇടമില്ലാതെ പ്രശ്നം പരിഹരിക്കുന്നതിന്. ബൈനറി കൃത്രിമത്വത്തിൽ നിന്ന് ഞങ്ങൾ സഹായം സ്വീകരിക്കേണ്ടതുണ്ട്. ഈ അൽ‌ഗോരിതം പലപ്പോഴും കാണാത്തതിനാൽ ഇത് ഒരു ട്രിക്ക് പോലെ തോന്നാം. അതിനാൽ ഈ പ്രശ്നങ്ങൾ അഡ്‌ഹോക് വിഭാഗത്തിൽ പെടുന്നു. പ്രശ്നം പരിഹരിക്കാനുള്ള ആദ്യപടി ആദ്യ, രണ്ടാം പകുതിയിൽ നിന്നുള്ള ഘടകങ്ങൾ എങ്ങനെയെങ്കിലും സംയോജിപ്പിച്ച് രണ്ടാം പകുതിയിലേക്ക് മാറ്റുക എന്നതാണ്. എന്നാൽ ഈ സംയോജനം എന്താണ് അർത്ഥമാക്കുന്നത്? ഞങ്ങൾ ആദ്യം ഘടകങ്ങൾ രണ്ടാം പകുതിയിൽ നിന്ന് ഇടത്തേക്ക് (ഇടത് ബൈനറി ഷിഫ്റ്റ്) 10 ബിറ്റുകൾ വഴി മാറ്റുന്നു. ഒന്നുകിൽ ഞങ്ങൾ ആദ്യ പകുതിയിലെ ഘടകങ്ങൾ ചേർക്കുന്നു അല്ലെങ്കിൽ ആദ്യ പകുതിയുടെ ഘടകങ്ങളുമായി OR എടുക്കുന്നു. അതിനാൽ ഇപ്പോൾ ഘടകങ്ങൾ സംയോജിപ്പിച്ചിരിക്കുന്നു.

ഇപ്പോൾ യഥാർത്ഥ അറേയിലൂടെ സഞ്ചരിക്കുക. ഓരോ ആവർത്തനത്തിലും 2 ഘട്ടങ്ങൾ വർദ്ധിപ്പിക്കുന്ന ഒരു ഫോർ ലൂപ്പ് ഞങ്ങൾ ആരംഭിക്കുന്നു. ഓരോ ഘട്ടത്തിലും ഞങ്ങൾ രണ്ടാം പകുതിയിൽ നിന്ന് ഒരു ഘടകം തിരഞ്ഞെടുത്ത് ഈ സ്ഥലങ്ങളിലെ ഘടകങ്ങളെ xi, yi ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുന്നു. ആദ്യ മൂലകം ലഭിക്കുന്നതിന് ആദ്യ പകുതിയും 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), അറേയിലെ ഓരോ ഘടകങ്ങളും ഞങ്ങൾ സഞ്ചരിക്കുന്നതിനാൽ. ഞങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെങ്കിലും 2n മൂലകങ്ങൾ, സമയ സങ്കീർണ്ണത ഇപ്പോഴും O (N) ആയി തുടരുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), അൽ‌ഗോരിതം ഒരു സ്ഥലത്തുള്ള അൽ‌ഗോരിതം ആണ്. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും സ്ഥിരമാണ്.