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

2020-11-03

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

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

请你返回目标数组。

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

思路：找到下标 index[i] ，将 index[i] 后面的元素移动到 index[i] + 1 后面。可以使用顺序表先存储答案，顺序表插入元素就可以实现将前面的元素后移。比如 python 元组的 insert 方法，java arrylist 的 add 方法。

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

    // 把 list 转化为 array
    int[] res = new int [len];
    for(int i=0;i<len;i++){
        res[i] = list.get(i);
    }

    return res;
}

记数组长度为 n

时间复杂度

空间复杂度：没有使用到辅助空间，空间复杂度为 1

方法二

因为 index 数组的元素可能存在重复值，重复 index 对应的元素值不相等，最新重复的元素会替换上一次重复的元素，上一次重复的元素需要后移一位。

因为可以先对 index 数组从新整理，比当前 index 大于或者小于的 index 都++，这样就可以保持最新的 index 一直是当前位置，重复值就在其后，大于它的值也在后面。

int len = nums.length;
int[] target = new int[len];
// 先对index 数组整理
for(int i = 0; i < len; i++) {
    for(int j = 0; j < i; j++) {
        if(index[j] >= index[i]) {
        index[j]++;
   	 }
	}
}
// 
for(int i = 0; i < len; i++) {
	target[index[i]] = nums[i];
}
return target;

记数组长度为 n

时间复杂度：考虑一次操作最坏情况下的时间代价和当前数组中元素的个数呈正比，第 i 次操作时元素的个数为 i - 1，所以渐进事件复杂度为

空间复杂度：没有使用到辅助空间，空间复杂度为 1