LeetCode刷题（67）～新排列数组【大佬的算法就是强啊 非常值得学习！！！】

题目描述

给你一个数组 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]

  

 

  
1
  
2
  
3
 

示例 2：

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

  

 

  
1
  
2
 

示例 3：

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

  

 

  
1
  
2
 

提示：

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

解答 By 海轰

提交代码

vector<int> shuffle(vector<int>& nums, int n) { vector<int> result; for(int i=0;i<n;++i) { result.push_back(nums[i]); result.push_back(nums[i+n]); } return result; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

运行结果

解答

Demo

vector<int> shuffle(vector<int>& nums, int n) { for(int i = 0; i < 2 * n; i ++){ int j = i < n ? 2 * i : 2 * (i - n) + 1; nums[j] |= (nums[i] & 1023) << 10; } for(int& e: nums) e >>= 10; return nums; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

运行结果

Demo

vector<int> shuffle(vector<int>& nums, int n) { for(int i = 0; i < 2 * n; i ++) if(nums[i] > 0){ // j 描述当前的 nums[i] 对应的索引，初始为 i int j = i; while(nums[i] > 0){ // 计算 j 索引的元素，也就是现在的 nums[i]，应该放置的索引 j = j < n ? 2 * j : 2 * (j - n) + 1; // 把 nums[i] 放置到 j 的位置， // 同时，把 nums[j] 放到 i 的位置，在下一轮循环继续处理 swap(nums[i], nums[j]); // 使用负号标记上，现在 j 位置存储的元素已经是正确的元素了 nums[j] = -nums[j]; } } for(int& e: nums) e = -e; return nums; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

运行结果

来自大佬的算法：算法详解😆

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shuffle-the-array
参考：https://leetcode-cn.com/problems/shuffle-the-array/solution/kong-jian-fu-za-du-wei-o1-de-liang-chong-jie-fa-by/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108058159