[LeetCode]977. Squares of a Sorted Array

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：546 字 | 阅读时长：3 分钟

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:

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

Example 2:

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

Note:

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

大概解释下题目：有序的有符号数组元素平方后排序。

方案一

思路：迭代循环每个元素进行平方，然后再用sort排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        unsigned int size = A.size();
        for (unsigned int i = 0; i < size; ++i) {
            A[i] = A[i]*A[i];
        }
        sort(A.begin(), A.end());
        return A;
    }
};

result

Runtime: 124 ms, faster than 45.70% of C++ online submissions for Squares of a Sorted Array.

Memory Usage: 13.4 MB, less than 100.00% of C++ online submissions for Squares of a Sorted Array.

内存占用效果不错，但是执行效率就差了，for循环的原因？

方案二

新建一个数组替换原来的A

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        unsigned int len = A.size();
        vector<int> out(len);
        for (unsigned int i = 0; i < len; ++i) {
            out[i] = A[i]*A[i];
        }
        sort(out.begin(), out.end());
        return move(out);
    }
};

result

Runtime: 120 ms, faster than 58.11% of C++ online submissions for Squares of a Sorted Array.

Memory Usage: 13.5 MB, less than 99.64% of C++ online submissions for Squares of a Sorted Array.

效果并没有好多少。

方案三

读题不够仔细，原始数组就是有序的，只不过是包含了负数而已，这个排序就可以用来比较了，以下这个方案是讨论区的答案，有点巧妙。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> out(A.size());
        for (int pn = 0, pp = A.size() - 1, pos = A.size() - 1; pn <= pp; --pos) {
            out[pos] = pow(abs(A[pn]) < abs(A[pp]) ? A[pp--] : A[pn++], 2);
        }  
        return out;
    }
};

result

Runtime: 100 ms, faster than 98.97% of C++ online submissions for Squares of a Sorted Array.

Memory Usage: 13.3 MB, less than 100.00% of C++ online submissions for Squares of a Sorted Array.

执行效率和内存占用表现都相当好；

tip

后续类似循环的题目，最高的效率就是要在同一个循环里面，把多件事同时做了。