运维开发网

测试面试LeetCode系列:按既定顺序创建目标数组

运维开发网 https://www.qedev.com 2020-12-24 09:00 出处:51CTO 作者:测试生财
题目给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组:目标数组 target 最初为空。按从左到右的顺序依次读取 nums[i] 和 index[i],在 target 数组中的下标 index[i] 处插入值 nums[i] 。重复上一步,直到在 nums 和 index 中都没有要读取的元素。请你返回目标数组。题目保证数字插入位置总是存在。示例 1:输入:nums =

题目

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组:

  • 目标数组 target 最初为空。
  • 按从左到右的顺序依次读取 nums[i] 和 index[i],在 target 数组中的下标 index[i] 处插入值 nums[i] 。
  • 重复上一步,直到在 nums 和 index 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1:

输入:nums = [0,1,2,3,4], index = [0,1,2,2,1]

输出:[0,4,1,3,2]

解释:

nums index target

0    0   [0]

1   1   [0,1]

2  2   [0,1,2]

3    2   [0,1,3,2]

4    1   [0,4,1,3,2]

示例 2:

输入:nums = [1,2,3,4,0], index = [0,1,2,3,0]

输出:[0,1,2,3,4]

解释:

nums index target

1   0   [1]

2   1   [1,2]

3   2    [1,2,3]

4   3    [1,2,3,4]

0   0    [0,1,2,3,4]

示例 3:

输入:nums = [1], index = [0]

输出:[1]

提示:

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i 

来源:力扣(LeetCode)

思路

先初始化一个数组target,全部用-1填充,然后用下标i循环遍历数组index和nums。

如果target[index[i]]为-1,说明这个位置没有插入过数字,直接复制target[index[i]] = nums[i]即可。

如果target[index[i]]不为-1,说明这个位置已经插入过数字,那么需要要将targer数组的index..length这段元素依次往后移动一位,然后再设置target[index[i]] = nums[i]。

循环次数 nums index target

0     1   0   [1]

1     2   1   [1,2]

2     3   2   [1,2,3]

3     4   3   [1,2,3,4]

4     0   0   [0,1,2,3,4]

实现方式

class Solution(object):

    def createTargetArray(self, nums, index):

        """

        :type nums: List[int]

        :type index: List[int]

        :rtype: List[int]

        """

        length = len(nums)
     #初始化目标target数组
        target = [-1] * length
        #下标法遍历两个数组
        for i in range(length):
            #如果target的下标为index[i]的位置没有插入过数字
            if target[index[i]] == -1:
                #直接复制num[i]给target[index[i]]
                target[index[i]] = nums[i]
            else:
          #将下标为index[i]到length-1处的元素后移
                for j in range(length-1, index[i], -1):
                    target[j] = target[j-1]
                #后移完之后在复制target[index[i]]
                target[index[i]] = nums[i]
        return target

各位大神,有其他思路欢迎留言~

博主:测试生财

座右铭:专注测试与自动化,致力提高研发效能;通过测试精进完成原始积累,通过读书理财奔向财务自由。

csdn:https://blog.csdn.net/ccgshigao

博客园:https://www.cnblogs.com/qa-freeroad/

51cto:https://blog.51cto.com/14900374

0

精彩评论

暂无评论...
验证码 换一张
取 消