1470. 重新排列数组：
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
样例 1
输入：
nums = [2,5,1,3,4,7], n = 3
输出：
[2,3,5,4,1,7]
解释：
由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=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
分析
- 这道算法题是简单题，所以又可以重拳出击了。
- 返回的结果不算在空间复杂度上，所以直接开辟新的空间赋值返回结果就可以了。
- 但是二当家的发现可以难为自己，于是又灵机一动，原地排列，我真是个小机灵鬼。
- 想要原地排列就一定要存储中间结果，原来的位置被占以后，需要知道原来位置的数字。
- 提示里说每个数字最大不超过1000，而且都是正数，所以只需要用10个二进制位就够了。
- 参数传递进来的数组一般都是int型数组，int型一般都是32位，够存题目中的2个数了。
题解
java
class Solution {
public int[] shuffle(int[] nums, int n) {
// 申请新的数组，这样用空间换时间
int[] ans = new int[n * 2];
for (int i = 0; i < n; ++i) {
ans[2 * i] = nums[i];
ans[2 * i + 1] = nums[n + i];
}
return ans;
}
}class Solution {
public int[] shuffle(int[] nums, int n) {
// 原地排列，时间换空间
for (int i = 0; i < n; ++i) {
// 把重排列的值左移10位
nums[2 * i] |= (nums[i] & 0b1111111111) << 10;
nums[2 * i + 1] |= (nums[n + i] & 0b1111111111) << 10;
}
// 将结果右移10位，低10位的原值没用了
for (int i = 0; i < n; ++i) {
nums[2 * i] >>= 10;
nums[2 * i + 1] >>= 10;
}
return nums;
}
}c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* shuffle(int* nums, int numsSize, int n, int* returnSize){
// 申请新的数组，这样用空间换时间
int *ans = (int *) malloc(sizeof(int) * numsSize);
for (int i = 0; i < n; ++i) {
ans[2 * i] = nums[i];
ans[2 * i + 1] = nums[n + i];
}
*returnSize = numsSize;
return ans;
}/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* shuffle(int* nums, int numsSize, int n, int* returnSize){
// 原地排列，时间换空间
for (int i = 0; i < n; ++i) {
// 把重排列的值左移10位
nums[2 * i] |= (nums[i] & 0b1111111111) << 10;
nums[2 * i + 1] |= (nums[n + i] & 0b1111111111) << 10;
}
// 将结果右移10位，低10位的原值没用了
for (int i = 0; i < n; ++i) {
nums[2 * i] >>= 10;
nums[2 * i + 1] >>= 10;
}
*returnSize = numsSize;
return nums;
}c++
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
// 申请新的数组，这样用空间换时间
vector<int> ans;
for (int i = 0; i < n; ++i) {
ans.push_back(nums[i]);
ans.push_back(nums[n + i]);
}
return ans;
}
};class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
// 原地排列，时间换空间
for (int i = 0; i < n; ++i) {
// 把重排列的值左移10位
nums[2 * i] |= (nums[i] & 0b1111111111) << 10;
nums[2 * i + 1] |= (nums[n + i] & 0b1111111111) << 10;
}
// 将结果右移10位，低10位的原值没用了
for (int i = 0; i < n; ++i) {
nums[2 * i] >>= 10;
nums[2 * i + 1] >>= 10;
}
return nums;
}
};python
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
# 申请新的数组，这样用空间换时间
ans = []
for i in range(n):
ans.append(nums[i])
ans.append(nums[n + i])
return ansclass Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
# 原地排列，时间换空间
for i in range(n):
# 把重排列的值左移10位
nums[2 * i] |= (nums[i] & 0b1111111111) << 10;
nums[2 * i + 1] |= (nums[n + i] & 0b1111111111) << 10
# 将结果右移10位，低10位的原值没用了
for i in range(n):
nums[2 * i] >>= 10
nums[2 * i + 1] >>= 10
return numsgo
func shuffle(nums []int, n int) []int {
// 申请新的数组，这样用空间换时间
ans := make([]int, 0, n*2)
for i := 0; i < n; i++ {
ans = append(ans, nums[i], nums[n+i])
}
return ans
}func shuffle(nums []int, n int) []int {
// 原地排列，时间换空间
for i := 0; i < n; i++ {
// 把重排列的值左移10位
nums[2*i] |= (nums[i] & 0b1111111111) << 10
nums[2*i+1] |= (nums[n+i] & 0b1111111111) << 10
}
// 将结果右移10位，低10位的原值没用了
for i := 0; i < n; i++ {
nums[2*i] >>= 10
nums[2*i+1] >>= 10
}
return nums
}rust
impl Solution {
pub fn shuffle(nums: Vec<i32>, n: i32) -> Vec<i32> {
let n: usize = n as usize;
// 申请新的数组，这样用空间换时间
let mut ans = Vec::new();
(0..n).for_each(|i| {
ans.push(nums[i]);
ans.push(nums[n + i]);
});
ans
}
}impl Solution {
pub fn shuffle(nums: Vec<i32>, n: i32) -> Vec<i32> {
let mut nums = nums;
let n = n as usize;
// 原地排列，时间换空间
(0..n).for_each(|i| {
// 把重排列的值左移10位
nums[2 * i] |= (nums[i] & 0b1111111111) << 10;
nums[2 * i + 1] |= (nums[n + i] & 0b1111111111) << 10;
});
// 将结果右移10位，低10位的原值没用了
(0..n).for_each(|i| {
nums[2 * i] >>= 10;
nums[2 * i + 1] >>= 10;
});
nums
}
}
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
