CTF of Z2BNS
0%

按既定顺序创建目标数组

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
输入：nums = [1], index = [0]
输出：[1]

提示：

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

遍历，将每一个nums中的元素插入到目标数组中，相应的位置为index中元素的值。

c++代码：(执行用时4ms，击败69.65%，内存消耗8.5M，击败29.71%）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> result;
        for(int i=0;i<nums.size();++i){
            result.insert(result.begin()+index[i],nums[i]);
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：模拟
思路

使用顺序表作为答案的存储结构，按照题意模拟即可。具体的方法是：要在当前的下标从 $0$ 开始长度为 $n$ 的顺序表的 $i$ 位置插入元素，就要先把原来表中区间$[i, n]$中的元素从全部向后移动一位，然后在 $i$ 位置插入带插入的元素。当然很多语言中都有现成的方法可以调用，比如 C++ vector 类中的 insert、Python 列表中的 insert 等。

c++代码：(执行用时0ms，击败100.00%，内存消耗8.7M，击败5.43%）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector <int> r;
        for (unsigned i = 0; i < nums.size(); ++i) {
            r.insert(r.begin() + index[i], nums[i]);
        }
        return r;
    }
};

复杂度分析

记数组的长度为 $n$。

  • 时间复杂度：考虑一次操作最坏情况下的时间代价和当前数组中元素的个数呈正比， 第 $i$ 次操作时元素个数为 $i - 1$，所以这里渐进时间复杂度为 $O(\sum_{i = 1}^{n} (i - 1)) = O(n^2)$
  • 空间复杂度：这里没有使用到辅助空间，故渐进空间复杂度为 $O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

解题过程和官方题解一致，代码也几乎相同，应该是最优解了。

------------- THE END! THANKS! -------------