[LeetCode 977]PHP 实现有序数组的平方

码农天地 - 2020-09-18 13:28: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/probl...

解题思路 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;

    }

}

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

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。