PHP 实现有序数组的平方

PHP 实现有序数组的平方

author: he xiaodong date: 2020-09-15
有序数组的平方

给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

示例 1:

输入:[-4,-1,0,3,10]
输出:[0,1,9,16,100]

示例 2:

输入:[-7,-3,2,3,11]
输出:[4,9,9,49,121]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array

解题思路 1

内置函数求解

代码
class Solution {

    /**
     * @param Integer[] $A
     * @return Integer[]
     */
    function sortedSquares($A) {
        foreach ($A as &$item) {
            $item = $item * $item;
        }

        sort($A);
        return $A;
    }
}
解题思路 2

双指针遍历,同时借助新数组,将计算平方之后的结果从大到小放到新数组。

class Solution {

    /**
     *  ** 2 为自乘 2 次,也是平方
     * @param Integer[] $A
     * @return Integer[]
     */
    function sortedSquares($A) {
        $ans = [];
        $i = 0;
        $j = count($A) - 1;
        $k = count($A) - 1;
        while ($i <= $j) {
            // 原数组是有序的,所以 -$A[$i] > $A[$j] 即为 $A[$i] 的绝对值平方后更大 

            if (-$A[$i] > $A[$j]) {
                $ans[$k--] = $A[$i] ** 2;
                // 左指针向右移动
                
                $i++;
            } else {
                $ans[$k--] = $A[$j] ** 2;
                $j--;
            }
        }

        return $ans;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券