【算法学习】1470. 重新排列数组(java / c / c++ / python / go / rust)

简介: 给你一个数组 nums ,数组中有 2n 个元素,按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列,返回重排后的数组。

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 ans
class 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 nums

go

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 博客原创~

相关文章
|
2天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
|
3天前
|
算法 Go 分布式数据库
构建高可用的分布式数据库集群:使用Go语言与Raft共识算法
随着数据量的爆炸式增长,单一数据库服务器已难以满足高可用性和可扩展性的需求。在本文中,我们将探讨如何使用Go语言结合Raft共识算法来构建一个高可用的分布式数据库集群。我们不仅会介绍Raft算法的基本原理,还会详细阐述如何利用Go语言的并发特性和网络编程能力来实现这一目标。此外,我们还将分析构建过程中可能遇到的挑战和解决方案,为读者提供一个完整的实践指南。
|
3天前
|
机器学习/深度学习 算法 网络架构
什么是神经网络学习中的反向传播算法?
什么是神经网络学习中的反向传播算法?
9 2
|
4天前
|
机器学习/深度学习 算法
算法人生(5):从“元学习”看“战胜拖延”(没兴趣版)
元学习是让机器学会学习策略,适应新任务的机器学习范式。通过定义任务分布、采样任务、内在和外在学习循环来优化模型,增强其跨任务适应性和泛化能力。面对不感兴趣的任务导致的拖延,我们可以借鉴元学习的思路:重新评估任务价值,寻找通用兴趣点;设定奖励激发行动;改变环境以提高执行力。通过调整视角、自我激励和优化环境,可以克服因无兴趣而产生的拖延。
|
3天前
|
机器学习/深度学习 存储 算法
算法人生(4):从“选项学习”看“战胜拖延”(担心失败版)
选项学习是强化学习的一种策略,通过定义、学习和切换选项来解决复杂任务,将大任务分解为可重复使用的子任务,以提高学习效率和适应性。面对因担心失败而拖延的问题,我们可以借鉴选项学习的思想:将大任务拆分为小目标,正视失败作为成长的一部分,回顾成功经验并寻求支持。通过这种方式,逐步增强自信,降低拖延现象。
|
4天前
|
算法 网络协议
【计网·湖科大·思科】实验三 总线型以太网的特性、集线器和交换机的区别、交换机的自学习算法
【计网·湖科大·思科】实验三 总线型以太网的特性、集线器和交换机的区别、交换机的自学习算法
8 1
|
3天前
|
存储 编译器 Go
Go语言学习12-数据的使用
【5月更文挑战第5天】本篇 Huazie 向大家介绍 Go 语言数据的使用,包含赋值语句、常量与变量、可比性与有序性
50 6
Go语言学习12-数据的使用
|
3天前
|
机器学习/深度学习 算法
应用规则学习算法识别有毒的蘑菇
应用规则学习算法识别有毒的蘑菇
|
4天前
|
Java Go
Go语言学习11-数据初始化
【5月更文挑战第3天】本篇带大家通过内建函数 new 和 make 了解Go语言的数据初始化过程
29 1
Go语言学习11-数据初始化
|
4天前
|
JavaScript 前端开发 Go
Go语言的入门学习
【4月更文挑战第7天】Go语言,通常称为Golang,是由Google设计并开发的一种编程语言,它于2009年公开发布。Go的设计团队主要包括Robert Griesemer、Rob Pike和Ken Thompson,这三位都是计算机科学和软件工程领域的杰出人物。
17 1