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
分析
- 这道算法题只要按照题意模拟就可以了。
- 我们经常去比较数组和链表：数组遍历和修改数据高效，链表增加和删除数据高效；另外链表需要维护其他节点的地址，所以内存空间占用更多一些。
- 这道题也同样面临着这个问题，由于题目要求按照下标插入数据，如果使用数组，定位到下标指定位置很快，但是在中间位置插入数据会涉及到数据的移动，这是很费时的；如果使用链表，在中间位置添加数据不需要大段数据的移动就很快，但是需要先遍历到指定下标位置又会比较慢。
- 而且像Java语言的题解，最终结果要的是数组，而中间使用了List，这就涉及到最终需要转换，也需要遍历。所以到底是ArrarList更快还是LinkedList更快就难说了，会和具体参数有关。
- 像C语言的题解，直接用原生数组，所以要自己实现数据移动的逻辑。
题解
java
class Solution {
public int[] createTargetArray(int[] nums, int[] index) {
int n = nums.length;
List<Integer> t = new ArrayList<>();
for (int i = 0; i < n; ++i) {
t.add(index[i], nums[i]);
}
int[] ans = new int[n];
int i = 0;
for (Integer num : t) {
ans[i++] = num;
}
return ans;
}
}c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* returnSize){
int *ans = malloc(numsSize * sizeof(int));
*returnSize = numsSize;
for (int i = 0; i < numsSize; ++i) {
for (int j = i; j > index[i]; --j) {
ans[j] = ans[j - 1];
}
ans[index[i]] = nums[i];
}
return ans;
}c++
class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
ans.insert(ans.begin() + index[i], nums[i]);
}
return ans;
}
};python
class Solution:
def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
ans = []
for i in range(len(nums)):
ans.insert(index[i], nums[i])
return ans
go
func createTargetArray(nums []int, index []int) []int {
ans := make([]int, len(nums))
for tail, i := range index {
if tail > i {
copy(ans[i+1:tail+1], ans[i:tail])
}
ans[i] = nums[tail]
}
return ans
}rust
impl Solution {
pub fn create_target_array(nums: Vec<i32>, index: Vec<i32>) -> Vec<i32> {
let mut ans = Vec::new();
nums.into_iter().zip(index.into_iter()).for_each(|(n, i)| {
ans.insert(i as usize, n);
});
ans
}
}
原题传送门：https://leetcode-cn.com/problems/create-target-array-in-the-given-order/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
