1389-按既定顺序创建目标数组

给你两个整数数组 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

方法一：模拟

思路

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

代码

[sol1-C]

int* createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * indexSize);
    int tail = -1;
    for (int i = 0; i < indexSize; ++i) {
        ++tail;
        for (int j = tail; j > index[i]; --j) {
            ret[j] = ret[j - 1];
        }
        ret[index[i]] = nums[i];
    }
    *returnSize = indexSize;
    return ret;
}

[sol1-C++]

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;
    }
};

[sol1-Java]

class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; ++i) {
            list.add(index[i], nums[i]);
        }
        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

[sol1-Python]

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        ret = []
        for i in range(len(nums)):
            ret.insert(index[i], nums[i])
        return ret

复杂度分析

记数组的长度为 n。

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

• 空间复杂度：这里没有使用到辅助空间，故渐进空间复杂度为 O(1)。