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

更多内容关注个人博客：lemonlyue.github.io/

题目

• 难度：简单

• 题目链接：leetcode-cn.com/problems/create-ta...

• 语言： 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]

解释：

示例 2：

输入：nums = [1,2,3,4,0], index = [0,1,2,3,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), 然后通过该映射写入到结果中。

题解链接：leetcode-cn.com/problems/create-ta...

运行结果如下：

本作品采用《CC 协议》，转载必须注明作者和本文链接