Перемешать решение Leetcode для массива


Сложный уровень Легко
Часто спрашивают в саман Apple Bloomberg Google Microsoft
массив

Задача Перемешать массив. Решение Leetcode предоставляет нам массив длиной 2n. Здесь 2n означает, что массив длина ровная. Затем нам говорят перетасовать массив. Здесь перемешивание не означает, что нам нужно случайным образом перемешать массив, но показан конкретный способ. Если данный массив может быть представлен как [x1, x2,…, y1, y2,…], то перетасовка будет представлена ​​как [x1, y1, x2, y2,…]. Таким образом, проблема довольно проста и не требует от нас каких-либо решений. Нам просто нужно найти способ поменять местами элементы, чтобы получить требуемую последовательность. Также есть одно ограничение на ввод, входные элементы меньше 10 ^ 3. Но прежде чем углубиться в решение, давайте рассмотрим несколько примеров.

Перемешать решение Leetcode для массива

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

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

Подход к перемешиванию решения Leetcode для массива

Проблема Shuffle the Array Leetcode Solution просит перетасовать массив определенным образом. Режим перетасовки требует, чтобы мы поместили элементы последней половины массива между элементами первой половины. Более формально, массив [x1, x2, x3,…, y1, y2, y3,…] должен быть перемешан как [x1, y1, x2, y2, x3, y3,… xn, yn]. Так что проблему легко решить с помощью дополнительного места. Потому что тогда мы можем просто создать новый массив той же длины, что и исходный. И вытолкните элементы из первой половины, затем из второй. Таким образом, мы получаем требуемый массив.

Чтобы решить проблему без дополнительного места в пространстве O (1). Нам нужна помощь от двоичных манипуляций. Это может показаться уловкой, потому что такие алгоритмы встречаются нечасто. Таким образом, эти проблемы подпадают под категорию специальных. Первый шаг к решению задачи - каким-то образом объединить элементы из первой и второй половин во вторую половину. Но что означает этот КОМБИНАТ? Сначала сдвигаем элементы из второй половины влево (двоичный сдвиг влево) на 10 бит. Затем мы либо складываем элементы первой половины, либо берем ИЛИ элементов второй половины с элементами первой половины. Итак, теперь элементы объединены.

Теперь просто пройдитесь по исходному массиву. Мы запускаем цикл for, который увеличивает на 2 шага в каждой итерации. На каждом шаге мы выбираем элемент из второй половины и заменяем элементы в этих местах на xi, yi. Мы можем получить xi, yi, сначала взяв AND элементов во второй половине с 2 ^ 10-1, чтобы получить первый элемент. Что касается второго элемента, мы сдвигаем каждый элемент вправо на 10 бит.

Код для перемешивания массива Leetcode Solution

Код 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), алгоритм представляет собой алгоритм на месте. Таким образом, сложность пространства также постоянна.