What is the time complexity of the Shuffle the Array problem?

The time complexity is O(n), where n is the size of the half array, as each element is processed once.

Can I solve the problem in-place?

Yes, the problem can be solved in-place with O(1) space complexity by modifying the array while rearranging elements.

What is the optimal solution for the Shuffle the Array problem?

The optimal solution uses a two-pointer approach to rearrange the elements in a single pass, ensuring O(n) time complexity.

Can this problem be extended to more than two halves?

Yes, the approach can be generalized to handle more than two halves by using additional pointers for each half.

What are the common mistakes when solving the Shuffle the Array problem?

Common mistakes include failing to properly pair elements from the two halves and using unnecessary space for the solution.

#1470

Easy

auto_awesome数组·driven

LeetCode 题解工作台

重新排列数组

给你一个数组 nums ，数组中有 2n 个元素，按 [x 1 ,x 2 ,...,x n ,y 1 ,y 2 ,...,y n ] 的格式排列。请你将数组按 [x 1 ,y 1 ,x 2 ,y 2 ,...,x n ,y n ] 格式重新排列，返回重排后的数组。示例 1：输入： nums =…

数组

题目描述

给你一个数组 nums ，数组中有 2n 个元素，按 [x₁,x₂,...,x_n,y₁,y₂,...,y_n] 的格式排列。

请你将数组按 [x₁,y₁,x₂,y₂,...,x_n,y_n] 格式重新排列，返回重排后的数组。

示例 1：

输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7] 
解释：由于 x₁=2, x₂=5, x₃=1, y₁=3, y₂=4, y₃=7 ，所以答案为 [2,3,5,4,1,7]

示例 2：

输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]

示例 3：

输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]

提示：

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3

lightbulb

解题思路

方法一：模拟

我们在 $[0, n)$ 的范围内遍历下标 $i$ ，每次取出 $\textit{nums}[i]$ 和 $\textit{nums}[i+n]$ ，并将它们依次放入答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        return [x for pair in zip(nums[:n], nums[n:]) for x in pair]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate come up with a solution that processes the array in a single pass?
question_mark
Does the candidate understand how to implement a two-pointer strategy?
question_mark
Can the candidate handle space constraints by modifying the array in place?

warning

常见陷阱

外企场景

error
Failing to handle the rearrangement correctly and ending up with an incorrect order.
error
Using unnecessary extra space when the problem can be solved in-place.
error
Not maintaining the correct pairing between elements from the two halves of the array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains more than two halves? Extend the problem to more parts.
arrow_right_alt
What if the array elements are not strictly consecutive or are unsorted?
arrow_right_alt
What if the input array is already partially shuffled? How would you handle this case?

help

常见问题

外企场景

继续练习

#1471 数组中的 k 个最强值 #1472 设计浏览器历史记录 #1467 两个盒子中球的颜色数相同的概率