拖曳阵列Leetcode解决方案


难度级别 易得奖学金
经常问 土砖 Apple 彭博 谷歌 微软
排列

随机排列数组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解决方案的方法

随机排列阵列Leetcode解决方案的问题要求以特定方式随机排列阵列。 混洗方式要求我们将数组的后一半元素放在前一半元素之间。 更正式地说,数组[x1,x2,x3,…,y1,y2,y3,…]将被洗牌为[x1,y1,x2,y2,x3,y3,…xn,yn]。 因此,借助额外的空间,可以轻松解决该问题。 因为这样我们可以简单地创建一个长度与原始数组相同的新数组。 并从上半年然后下半年推元素。 这样,我们最终得到所需的数组。

要解决此问题,而无需使用O(1)空间中的任何其他空间。 我们需要二进制操作的帮助。 这似乎是一个把戏,因为这些算法并不经常出现。 因此,这些问题属于临时类别。 解决该问题的第一步是以某种方式将第一部分和第二部分中的元素组合到第二部分中。 但是这个COMBINE是什么意思? 我们首先将元素从后半部分向左移位(左二进制移位)10位。 然后,要么将上半部分的元素相加,要么将下半部分的元素与上半部分的元素进行“或”运算。 因此现在将元素组合在一起。

现在,只需遍历原始数组即可。 我们开始一个for循环,该循环在每次迭代中增加2个步骤。 在每个步骤中,我们从后半部分中选择一个元素,然后将这些位置的元素替换为xi,yi。 我们可以通过先取后半部分中元素的AND与2 ^ 10-1来获得xi,yi,以获得第一个元素。 至于第二个元素,我们将每个元素右移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), 该算法是就地算法。 因此,空间复杂度也是恒定的。