Мешајте го решението за низа кодови во низата


Ниво на тешкотија Лесно
Често прашувано во Adobe Јаболко Блумберг Google Мајкрософт
Низа

Проблемот Shuffle the Array Leetcode Solution ни обезбедува низа со должина 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]

Објаснување: Ние лесно проверуваме дека резултатот ги задоволува бараните критериуми како што е наметнато во проблемот. Ако на елементите од низата им доделиме именување како x1, x2, до y3. Можеме да видиме дека елементите сега се распоредени во мода [x1, y1, x2, y2, x3, y3].

Пристап за мешање на решението за низа кодови во низата

Проблемот Shuffle Array Leetcode Solution бара да се помеша низата на специфичен начин. Модната мешаница бара од нас да ги поставиме елементите на последната половина помеѓу елементите на првото полувреме. Поформално, низата [x1, x2, x3,…, y1, y2, y3,…] треба да се меша како [x1, y1, x2, y2, x3, y3,… xn, yn]. Значи, лесно може да се реши проблемот со помош на дополнителен простор. Затоа што тогаш можеме едноставно да создадеме нова низа со иста должина како и онаа на оригиналната. И потиснете ги елементите од првата, а потоа од втората половина. На овој начин завршуваме со потребната низа.

Да се ​​реши проблемот без дополнителен простор што е во просторот О (1). Треба да земеме помош од бинарна манипулација. Ова може да изгледа како трик бидејќи овие алгоритми не се гледаат многу често. Така, овие проблеми спаѓаат во категоријата ад-хок. Првиот чекор за решавање на проблемот е некако да се комбинираат елементите од првата и втората половина во втората половина. Но, што значи овој КОМБИНА? Ние прво ги поместуваме елементите од втората половина налево (лево бинарна смена) за 10 бита. Потоа или ги додаваме елементите на првата половина или земаме ИЛИ на елементите од втората половина со елементите на првото полувреме. па сега елементите се комбинираат.

Сега едноставно поминете низ оригиналната низа. Започнуваме циклус за зголемување што се зголемува со 2 чекори во секоја повторување. Во секој чекор избираме елемент од втората половина и ги заменуваме елементите на овие места со xi, yi. Xi, yi можеме да ги добиеме со тоа што прво ќе земеме И од елементите во втората половина со 2 ^ 10-1 за да го добиеме првиот елемент. Што се однесува до вториот елемент, секој елемент десно го поместуваме за 10 бита.

Код за мешање на решението за низа кодови во низата

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

Java код

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).

Комплексноста на просторот

О (1), алгоритмот е алгоритам на место. Така, вселенската комплексност е исто така постојана.