LeetCode 每日一题(day 1)
作 者:
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
题目
题目描述:
给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
示例 1:
1 | 输入:[-4,-1,0,3,10] |
示例 2:
1 | 输入:[-7,-3,2,3,11] |
提示:
- 1<= A.length <= 10000
- -10000 <= A[i] <= 10000
- A 已按非递减顺序排序。
解决方案
方法一:排序
思路与算法
创建一个新的数组,它每个元素是给定数组对应位置元素的平方,然后排序这个数组。
1 | public int[] sortedSquares(int[] A) { |
复杂度分析
时间复杂度:O(N \log N)O(NlogN),其中 NN 是数组 A 的长度。
空间复杂度:O(N)O(N)。
方法二:双指针
思路
因为数组 A 已经排好序了, 所以可以说数组中的负数已经按照平方值降序排好了,数组中的非负数已经按照平方值升序排好了。
举一个例子,若给定数组为 [-3, -2, -1, 4, 5, 6],数组中负数部分 [-3, -2, -1] 的平方为 [9, 4, 1],数组中非负部分 [4, 5, 6] 的平方为 [16, 25, 36]。我们的策略就是从前向后遍历数组中的非负数部分,并且反向遍历数组中的负数部分。
算法
我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分,指针 j 正向读取非负数部分。
那么,现在我们就在使用两个指针分别读取两个递增的数组了(按元素的平方排序)。接下来,我们可以使用双指针的技巧合并这两个数组。
1 | public int[] sortedSquares(int[] A) { |
作 者:
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。