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

题目

• 难度：简单
• 题目链接：https://leetcode-cn.com/problems/create-target-array-in-the-given-order/
• 语言： PHP
• 题目内容：
  给你两个整数数组 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]

解题

LeetCode给定函数体

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer[] $index
     * @return Integer[]
     */
    function createTargetArray($nums, $index) {
        
    }
}

思路

判断当前数组位置是否有值, 有值则将值往后移(递归思想), 没有值则插入

class Solution {

    /**
     * @desc 递归方法
     * @param Integer[] $nums
     * @param Integer[] $index
     * @return Integer[]
     */
    public $arr = [];
    function createTargetArray($nums, $index) {
        foreach ($index as $key => $item) {
            $this->insert($item, $nums[$key]);
        }
        return $this->$arr;
    }

    /**
     * @desc 插入方法, 判断当前数组位置是否有值, 有值则将值往后移, 没有值则插入
     * @param int $index
     * @param int $num
     */
    function insert($index, $num) {
        if (!isset($this->$arr[$index])) {
            $this->$arr[$index] = $num;
        } else {
            $temp = $this->$arr[$index];
            $this->insert($index + 1, $temp);
            $this->$arr[$index] = $num;
        }
    }
}

结果

使用递归方法，虽然说可以实现，但是耗时较长。有更好的解法可以在评论留言。

LeetCode其他题解

查看其他大佬分享题解，代码如下：

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer[] $index
     * @return Integer[]
     */
    function createTargetArray($nums, $index) {
        $target = [];

        $_tmp_indexs = [];
        foreach ($index as $i => $k) {
            if (in_array($k, $_tmp_indexs)) {
                foreach ($_tmp_indexs as &$_tmp_index) {
                    if ($_tmp_index >= $k) {
                        $_tmp_index ++;
                    }
                }
            }
            $_tmp_indexs[] = $k;
        }
        
        foreach ($_tmp_indexs as $i => $k) {
            $target[$k] = $nums[$i];
        }
        ksort($target);
        
        return $target;
    }
}

思路如下：
将index数组中的每一项遍历, 判断在插入后实际对应的下标位置得到($_tmp_index), 然后通过该映射写入到结果中。

题解链接：https://leetcode-cn.com/problems/create-target-array-in-the-given-order/solution/xian-chu-li-indexshu-zu-by-xiao-san-niang/

运行结果如下：