资讯专栏INFORMATION COLUMN

【算法学习】1920. 基于排列构建数组(java / c / c++ / python / go

aisuhua / 885人阅读

摘要:请你构建一个同样长度的数组,其中,对于每个,都满足。返回构建好的数组。从开始的排列是一个由到和也包含在内的不同整数组成的数组。

非常感谢你阅读本文,欢迎【?点赞】【⭐收藏】【?评论】~
放弃不难,但坚持一定很酷!希望我们大家都能每天进步一点点!?
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创,转载请注明来源,谢谢~



1920. 基于排列构建数组:

给你一个 从 0 开始的排列 nums(下标也从 0 开始)。请你构建一个 同样长度 的数组 ans ,其中,对于每个 i(0 <= i < nums.length),都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1(0 和 nums.length - 1 也包含在内)的不同整数组成的数组。

样例 1:

输入:	nums = [0,2,1,5,3,4]输出:	[0,1,2,4,5,3]解释:	数组 ans 构建如下:	ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]	    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]	    = [0,1,2,4,5,3]

样例 2:

输入:	nums = [5,0,1,2,3,4]输出:	[4,5,0,1,2,3]解释:	数组 ans 构建如下:	ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]	    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]	    = [4,5,0,1,2,3]

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < nums.length
  • nums 中的元素 互不相同

分析

题目描述既是答案,直接新建一个同样大小的数组,遍历一遍,按顺序赋值即可。

但是这样需要占更多内容空间,而且单纯这样做,根本算不上算法吧?

怎样能做到不占用新的内存空间呢?提示中,每个数的范围都在[0,999]之间,这是个关键。


题解

java

按照题意的直接处理法

class Solution {    public int[] buildArray(int[] nums) {        final int n = nums.length;                int[] ans = new int[n];                for (int i = 0; i < n; ++i) {            ans[i] = nums[nums[i]];        }                return ans;    }}

不开辟新的空间,直接在原数组处理

class Solution {    public int[] buildArray(int[] nums) {        final int n         = nums.length;        final int highValue = 1000;        // 将结果值附加到数组        for (int i = 0; i < n; ++i) {            // 将原值+结果            // 一个值同时存储了原值和结果值            nums[i] += highValue * (nums[nums[i]] % highValue);        }        // 将原值剔除,仅保留结果        for (int i = 0; i < n; ++i) {            nums[i] /= highValue;        }        return nums;    }}

c

/** * Note: The returned array must be malloced, assume caller calls free(). */int* buildArray(int* nums, int numsSize, int* returnSize){    const int highValue = 1000;    for (int i = 0; i < numsSize; ++i) {        nums[i] += highValue * (nums[nums[i]] % highValue);    }    for (int i = 0; i < numsSize; ++i) {        nums[i] /= highValue;    }    *returnSize = numsSize;    return nums;}

c++

class Solution {public:    vector<int> buildArray(vector<int>& nums) {        const int highValue = 1000;        int n = nums.size();        for (int i = 0; i < n; ++i) {            nums[i] += highValue * (nums[nums[i]] % highValue);        }                for (int i = 0; i < n; ++i) {            nums[i] /= highValue;        }        return nums;    }};

python

from typing import Listclass Solution:    def buildArray(self, nums: List[int]) -> List[int]:        highValue = 1000        n = len(nums)        for i in range(n):            nums[i] += highValue * (nums[nums[i]] % highValue)        for i in range(n):            nums[i] //= highValue        return nums

go

func buildArray(nums []int) []int {	highValue := 1000	n := len(nums)	for i := 0; i < n; i++ {		nums[i] += highValue * (nums[nums[i]] % highValue)	}	for i := 0; i < n; i++ {		nums[i] /= highValue	}	return nums;}

rust

impl Solution {    pub fn build_array(nums: Vec) -> Vec {        let mut nums = nums;                let high_value = 1000;        let n = nums.len();                for i in 0..n {            nums[i] += high_value * (nums[nums[i] as usize] % high_value);        }        for i in 0..n {            nums[i] /= high_value;        }        return nums;    }}

原题传送门


文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/119815.html

相关文章

  • SegmentFault 技术周刊 Vol.40 - 2018,来学习一门新的编程语言吧!

    摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...

    caspar 评论0 收藏0
  • SegmentFault 技术周刊 Vol.40 - 2018,来学习一门新的编程语言吧!

    摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...

    nihao 评论0 收藏0
  • SegmentFault 技术周刊 Vol.40 - 2018,来学习一门新的编程语言吧!

    摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...

    Drummor 评论0 收藏0
  • 算法学习】1486. 数组异或操作(java / c / c++ / python / go /

    摘要:数组定义为下标从开始且。请返回中所有元素按位异或后得到的结果。样例输入输出解释数组为,其中。为按位异或运算符。也就是只有是奇数并且是奇数的时候,最终结果的最低位才会是。 ...

    ztyzz 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<