CTF of Z2BNS
0%

有序数组的平方

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 905 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给定一个按非递减顺序排序的整数数组 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 已按非递减顺序排序。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

遍历每一行，然后对每一行中的元素翻转交换元素的值（swap函数），再反转元素的值，注意特殊情况，矩阵行数为奇数时中间元素要特殊处理反转一次。

c++代码：(执行用时136ms，击败27.35%，内存消耗24.9M，击败41.18%）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for(int i=0;i<A.size();++i){
            A[i]=pow(A[i],2);
        }
        //对新数组非递减排序
        sort(A.begin(),A.end());
        return A;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一： 模拟

我们可以不使用额外的（非常数）空间来完成翻转和反转操作。对于 A[i][j]​，我们将它和 A[i][c - j - 1]​ 进行交换（即翻转），其中 c 是数组 A 的列数。在交换的同时，我们可以将这两个数进行反转。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int C = A[0].length;
        for (int[] row: A)
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }
        return A;
    }
}

复杂度分析

  • 时间复杂度：$O(M*N)$，其中 $M$ 和 $N$ 分别为数组 A 的行数和列数。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解和我的思路一样，不过对于特殊情况比我处理的好，也不算特殊情况吧，只是我自己把它当作特殊情况处理了，主要在于我使用了vector容器中的swap成员函数来交换两个元素，这样必须反转后覆盖原值，对于奇数行数矩阵的每行中间元素反转了两次，而采用tmp辅助变量来进行交换两个元素值不涉及到覆盖问题。其实就是太执着于STL模板库中的成员函数了，自己实现交换元素的功能也挺好，相当于对源码根据实际情况进行了改进，这样才能更灵活地处理问题。

------------- THE END! THANKS! -------------