LeetCode977解题思路

2019年06月20日 |

leetcode/ algorithm/ easy

| algorithm

原题

977. Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

解题思路

1. 题目条件是一个从小到大排序好的数组，并且要转化成平方值，所以遍历一遍是必须的，所以复杂度至少为O(n)。
2. 那么在上一条的基础上，我考虑的就是复杂度能不能降下来，质变的降低是不可能了，但是量上还是可以做文章的。
3. 经观察发现，输入条件是有正负数，所以越靠数组两端的绝对值越大，中间的越小。
   好了，就分析到这里，剩下的可以接着这个思路往下深想一下，基本就知道怎么写代码了。
   实在想不通再看眼代码，做个参考。

代码实现

Golang实现

https://github.com/cook-coder/my-leetcode-solution/tree/master/easy/977

成绩

成绩会有差异，仅供参考，重要的是要分析复杂度。