Разбъркайте Array Leetcode Solution


Ниво на трудност Лесно
Често задавани в Кирпич ябълка Bloomberg Google Microsoft
Array

Проблемът Shuffle the Array Leetcode Solution ни предоставя масив с дължина 2n. Тук 2n се позовава, че масив дължината е четна. След това ни се казва да разбъркаме масива. Тук разбъркването не означава, че трябва да разбъркваме произволно масива, но е показан специфичен начин. Ако даденият масив може да бъде представен като [x1, x2, ..., y1, y2, ...], тогава разбъркването е представено като [x1, y1, x2, y2, ...]. Така че проблемът е доста прав и не очаква да решим нищо. От нас просто се изисква да намерим някакъв начин за размяна на елементи, за да получим необходимата последователност. Освен това има едно ограничение за входа, входните елементи са по-малко от 10 ^ 3. Но преди да се потопите дълбоко в решението, нека вземем цикъл на няколко примера.

Разбъркайте Array Leetcode Solution

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

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

Подход за разбъркване на Array Leetcode Solution

Проблемът Разбъркайте Array Leetcode Solution изисква да разбъркате масива по специфичен начин. Разбъркващата мода ни моли да поставим последните половин елементи от масива между елементите на първата половина. По-формално, масив [x1, x2, x3,…, y1, y2, y3,…] трябва да бъде разбъркан като [x1, y1, x2, y2, x3, y3,… xn, yn]. Така че човек може лесно да реши проблема с помощта на допълнително пространство. Защото тогава можем просто да създадем нов масив със същата дължина като този на оригиналния. И натиснете елементите от първата половина, а след това от втората половина. По този начин завършваме с необходимия масив.

За решаване на проблема без допълнително пространство, което е в пространството O (1). Трябва да вземем помощ от бинарни манипулации. Това може да изглежда като трик, защото тези алгоритми не се виждат много често. По този начин тези проблеми попадат в категорията ad hoc. Първата стъпка за решаване на проблема е по някакъв начин да се комбинират елементите от първата и втората половина във втората половина. Но какво означава този КОМБИНАТ? Първо преместваме елементите от втората половина наляво (ляво двоично изместване) с 10 бита. Тогава или добавяме елементите от първата половина, или вземаме ИЛИ от елементите от втората половина с елементите от първата половина. така че сега елементите се комбинират.

Сега просто преминете през оригиналния масив. Стартираме цикъл for, който увеличава 2 стъпки във всяка итерация. Във всяка стъпка избираме елемент от втората половина и заместваме елементите на тези места с xi, yi. Можем да получим xi, yi, като първо вземем И на елементите през втората половина с 2 ^ 10-1, за да получим първия елемент. Що се отнася до втория елемент, ние изместваме всеки елемент надясно с 10 бита.

Код за разбъркване на решението Leetcode на масива

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

Сложност на пространството

O (1), алгоритъмът е алгоритъм на място. Така космическата сложност също е постоянна.