【力扣】977. 有序数组的平方

这道题大致有两种方法,一种是先循环再排序,一种是双指针比较后排序。

大家平时工作中会用哪种方法,请评论区告诉up,谢谢。

方法一: 普通先循环再排序(PHP)

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums) {
        foreach($nums as &$value) {
            $value = $value * $value;
        }
        unset($value);
        asort($nums);
        return $nums;
    }
}

解释: 利用PHP里的数组引用赋值 "&" 而非拷贝赋值方法,减少空间复杂度。

测试结果:

执行用时:72 ms, 在所有 PHP 提交中击败了59.44%的用户

内存消耗:18.3 MB, 在所有 PHP 提交中击败了6.29%的用户

通过测试用例:137 / 137

方法二: 利用双指针(PHP)

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums) {
        $length = count($nums) - 1;
        $res = [];
        $res = array_pad($res, $length, 1);
        for($i = 0, $j = $length, $pos = $length; $i <= $j; ) {
            if ($nums[$i] * $nums[$i] > $nums[$j] * $nums[$j]) {
                $res[$pos] = $nums[$i] * $nums[$i];
                ++$i;
            } else {
                $res[$pos] = $nums[$j] * $nums[$j];
                --$j;
            }
            --$pos;
        }
        return $res;
    }
}

解释: PHP在创建数组是不指定数组长度,是不是不能通过下标来插入元素。。。这里使用了 array_pad 来指定数组长度并且填充了占位元素。

测试结果:

执行用时:64 ms, 在所有 PHP 提交中击败了86.01%的用户

内存消耗:17.8 MB, 在所有 PHP 提交中击败了69.23%的用户

通过测试用例:137 / 137

 

上一篇:接口测试平台代码实现137: 小bug集中修复


下一篇:《算法竞赛进阶指南》 第二章 Acwing 137. 雪花雪花雪花 哈希