LeetCode面试系列 第12天:No.977 - 有序数组的平方_极客玩家大白

上一篇 LeetCode 面试题中,我们分析了一道集合相关的数学题。现在我们再来看一个排序相关的面试题吧~

Leetcode

今天要给大家分析的面试题是 LeetCode 上第 977 号问题,

LeetCode - 977. 有序数组的平方

https://leetcode-cn.com/problems/squares-of-a-sorted-array/

题目描述

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

示例 1:

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

示例 2:

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

提示:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

解题思路:

如果有办法将数组 A 中的值按绝对值进行递减序排序,那最后只需将排序过的数组中的每个数求个平方依次加入到结果 list 中即可。

恰好 Python 中的 sorted(array, key = abs) 可以实现按绝对值排序,所以这个问题就迎刃而解了。

AC的代码为:

1
2
3
4
5
6
7
class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        B = sorted(A, key = abs) # sort by absolute values
        res = list()
        for elem in B:
            res.append(elem*elem)
        return res

执行用时: 268 ms, 在所有 python3 提交中击败了 ` 87.52 %` 的用户.

Leetcode645

示例代码: https://github.com/JustDoPython/leetcode-python/tree/master/leetcode-977

版权声明


一个有故事的程序员

(转载本站文章请注明作者和出处 极客玩家大白

点击了解 :.NET技术人的网站


Show Disqus Comments

Post Directory