1470. 重新排列数组

水深无声 2022-12-08 14:26 160阅读 0赞

# 1.题目描述 #

给你一个数组 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.C++版本 #

## 2.1 开辟一个新vector：时间O(N) ##

#include <iostream>
    #include <vector>
    using namespace std;
    
    /*
    开辟一个新的vector来接收最后的ans结果
    执行用时：12 ms, 在所有 C++ 提交中击败了71.90%的用户
    内存消耗：9.8 MB, 在所有 C++ 提交中击败了18.98%的用户
    */
    vector<int> shuffle01(vector<int> &nums, int n)
    {
        vector<int> ans;
        for (int i = 0; i < n; i++)
        {
            ans.push_back(nums[i]);
            ans.push_back(nums[i + n]);
        }
        return ans;
    }
    
    int main()
    {
        int nums[4] = {1, 2, 4, 8};
        vector<int> vec(nums, nums + 4);
        int n = 2;
        vector<int> res = shuffle(vec, n);
        for (int i = 0; i < res.size(); i++)
        {
            cout << res[i];
        }
        cout << endl;
        return 0;
    }

## 2.2 在原来vector上操作 ##

#include <iostream>
    #include <vector>
    using namespace std;
    
    /*
    在元数组上进行操作
    执行用时：24 ms, 在所有 C++ 提交中击败了8.33%的用户
    内存消耗：9.6 MB, 在所有 C++ 提交中击败了60.64%的用户
    题解分析如下：
    n=2
        1 2 4 8 
    i=0 1 2 8 4 8
        1 2 8 4
    i=1 1 4 2 8 4
        1 4 2 8
    */
    vector<int> shuffle(vector<int> &nums, int n)
    {
        for (int i = 0; i < n; i++)
        {
            nums.insert(nums.begin() + n - i, nums.back());
            nums.pop_back();
        }
        return nums;
    }
    
    int main()
    {
        int nums[4] = {1, 2, 4, 8};
        vector<int> vec(nums, nums + 4);
        int n = 2;
        vector<int> res = shuffle(vec, n);
        for (int i = 0; i < res.size(); i++)
        {
            cout << res[i];
        }
        cout << endl;
        return 0;
    }

# 3.java版本 #

package com.array.easy.LeetCode1470;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     * @author GMT
     * @version 1.0
     * @create 2020-10-1818:07
     */
    public class Solution {
    
        /* 方法一：
         * 比较直接的想法是，分别按顺序取出这些数字放到list中，最后返回一个数组
         * 执行用时：3 ms, 在所有 Java 提交中击败了5.51%的用户
         * 内存消耗：38.7 MB, 在所有 Java 提交中击败了95.28%的用户
         * */
        public int[] shuffle1(int[] nums, int n) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length / 2; i++) {
                list.add(nums[i]);
                list.add(nums[i + n]);
            }
            int ans[] = new int[list.size()];
            for (int i = 0; i < list.size(); i++)
                ans[i] = list.get(i);
            return ans;
        }
    
        /*
         * 方法二：
         * 因为本身我们已经有了一个nums数组，我们不必创建新的数组，但是好像执行用时和内存消耗没啥变化
         * 执行用时：3 ms, 在所有 Java 提交中击败了5.51%的用户
         * 内存消耗：38.7 MB, 在所有 Java 提交中击败了92.35%的用户
         * */
        public int[] shuffle2(int[] nums, int n) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length / 2; i++) {
                list.add(nums[i]);
                list.add(nums[i + n]);
            }
            for (int i = 0; i < list.size(); i++)
                nums[i] = list.get(i);
            return nums;
        }
    
        /*
         * 方法三：直接用数组，不用list，答案是对的，只是这个时候传进去的nums数组已经发生了变化
         * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
         * 内存消耗：38.3 MB, 在所有 Java 提交中击败了99.52%的用户
         * */
        public int[] shuffle3(int[] nums, int n) {
            int[] ans = new int[2 * n];
            for (int i = 0; i < n; i++) {
                ans[2 * i] = nums[i];
                ans[2 * i + 1] = nums[i + n];
            }
            return ans;
        }
    
        public static void main(String[] args) {
            Solution solution = new Solution();
            int nums[] = {1, 3, 5, 2, 4, 6};
            int n = nums.length / 2;
            int ans1[] = solution.shuffle1(nums, n);
            System.out.print("经过方法一，ans1：");
            System.out.println(Arrays.toString(ans1));
            System.out.print("经过方法一，nums：");
            System.out.println(Arrays.toString(nums));
            int ans2[] = solution.shuffle2(nums, n);
            System.out.print("经过方法二，ans2：");
            System.out.println(Arrays.toString(ans2));
            System.out.print("经过方法二，nums：");
            // 事实上，函数对nums修改值，nums数组已经发生了变化
            // 参数传值：基本数据类型传递的是副本，引用数据类型跟着变化
            System.out.println(Arrays.toString(nums));
            int ans3[] = solution.shuffle3(nums, n);
            System.out.print("经过方法三，ans3：");
            System.out.println(Arrays.toString(ans3));
            System.out.print("经过方法三，nums：");
            System.out.println(Arrays.toString(nums));
        }
    }