Leetcode - Create Target Array in the Given Order

https://leetcode.com/problems/create-target-array-in-the-given-order/

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

• Initially target array is empty.
• From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
• Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
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]

It's like insert sort. Time complexity is O(n^2).

func createTargetArray(nums []int, index []int) []int {
    size := len(nums)
    result := make([]int, size)
    for i := 0; i < size; i++ {
        num := nums[i]
        insertPosition := index[i]
        move(result, insertPosition)
        result[insertPosition] = num
    }
    return result
}

func move(nums []int, start int) {
    for i := len(nums)-1; i > start; i-- {
        nums[i] = nums[i-1]
    }
}

• 相关文章
• 全局相关文章