LeetCode977.有序数组的平方（双指针法、暴力法、列表推导式）

1.问题描述

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4

示例 2：

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

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

2.解题思路

1. 暴力排序：每个数平方之后，排个序。
   时间复杂度：这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度
   空间复杂度：O(log⁡n)除了存储答案的数组以外，我们需要O(log⁡n)栈空间进行排序。
2. 双指针法：数组有序，平方后，数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。那么使用双指针，i指向起始位置，j指向终止位置。定义一个数组result，和A数组一样的大小，让k指向result数组终止位置。
   如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
   如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。
   时间复杂度：O(n)。其中n 是数组nums的长度。
   空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
   

3.代码

python：双指针法

from typing import List


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        k = len(nums) - 1
        # 创建一个与输入列表长度相等的列表，用于存储结果
        res = [0] * len(nums)
        # 定义两个指针 i 和 j，分别指向列表的首尾
        i, j = 0, len(nums) - 1
        while i <= j:
            # 如果左边指针的平方大于右边指针的平方
            if nums[i] ** 2 > nums[j] ** 2:
                # 将左边指针的平方存入结果列表的末尾
                res[k] = nums[i] ** 2
                # 左边指针向右移动一位
                i += 1
            else:
                # 将右边指针的平方存入结果列表的末尾
                res[k] = nums[j] ** 2
                # 右边指针向左移动一位
                j -= 1
            # 结果列表的索引向前移动一位
            k -= 1
        # 返回结果列表
        return res


arr = [-5, 3, 3, 4]
# 创建Solution类的实例
solution = Solution()
result = solution.sortedSquares(arr)
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

python：暴力排序+列表推导法

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)
1
2
3

python：暴力排序

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] *= nums[i]
        nums.sort()
        return nums
1
2
3
4
5
6

C++：双指针法

#include 
#include 
#include 

using namespace std;

class Solution {
	public:
		vector<int> sortedSquares(vector<int>& nums) {
			int k = nums.size() - 1;
			// 定义一个大小为原数组大小的，元素全部为 0 的新数组 res
			vector<int> res(nums.size(), 0);
			for(int i = 0, j = nums.size()-1; i <= j;) {
				if(nums[i] * nums[i] > nums[j] * nums[j]) {
					res[k] = nums[i] * nums[i];
					i++;
				} else {
					res[k] = nums[j] * nums[j];
					j--;
				}
				k--;
			}
			return res;
		}
};

int main() {
	Solution solution;
	vector<int> nums = {-4, -1, 0, 3, 10};
	vector<int> result = solution.sortedSquares(nums);

	cout << "Sorted Squares: ";
	for (int num : result) {
		cout << num << " ";
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

C++：暴力法

#include 
#include 
#include 

using namespace std;

class Solution {
	public:
		vector<int> sortedSquares(vector<int>& nums) {
			for(int i = 0; i < nums.size(); i++) {
				nums[i] *= nums[i];
			}
			sort(nums.begin(), nums.end());
			return nums;
		}
};

int main() {
	Solution solution;
	vector<int> nums = {-4, -1, 0, 3, 10};
	vector<int> result = solution.sortedSquares(nums);

	cout << "Sorted Squares: ";
	for (int num : result) {
		cout << num << " ";
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4.知识点

1. 结果数组初始化
   python：res = [0] * len(nums)是为了在循环中通过索引直接赋值给 res 的对应位置,以避免在循环中直接赋值，避免数组越界的情况。如果代码为res=[],res 是一个空列表，无法通过索引来直接进行赋值。因此，我们将 res 初始化为一个长度为 len(nums) 的列表，每个元素都初始化为 0。然后在循环中通过索引 k 对 res 进行赋值操作，把平方数按照逆序的方式存入 res 中。这样最后返回的 res 列表就是按照平方数递减顺序排列的结果。

   C++： vector res(nums.size(), 0); 创建一个大小与 nums 数组相等的向量 res，并将其所有元素初始化为 0。这样做是为了确保 res 向量的大小与 nums 数组一致，以便在后续的操作中能够正确地将平方值存储在正确的位置。如果使用 vector res; 来创建 res 向量，那么这个向量的大小将为 0，也就是空向量。在后续的索引赋值操作中，代码将会尝试将平方值存储在 res 向量的位置上，但是由于向量是空的，将无法执行这个操作。

2. 函数声明：-> 用于指定函数的返回值类型，在 List[int] 中，List 是返回值类型的一种注释，表示一个列表，int 则是列表中的元素类型，表示整数类型。

   def function_name(parameters: type) -> return_type:
       # 函数体
       return value
   1
   2
   3

3. from typing import List 语句的作用是导入 List 类型typing 模块提供了一组用于类型提示的类和函数，帮助开发者更好地定义函数参数、返回值的类型，提高代码的可读性、可靠性和可维护性。

4. python列表推导式 [expression for item in iterable if condition]
   其中，expression表示参与列表生成的表达式，可包含变量、函数调用等操作；item表示生成列表中的元素；iterable表示可迭代的对象，例如列表、元组、集合等；if condition表示对条件的筛选，可以省略。

5. C++ sort函数：sort(v.begin()，v.end()，cmp)
   它是用来对一组序列进行排序的。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，包含在头文件为#include的c++标准库中。 其有三个参数，前两个参数是待排序区间；第三个参数可有可无（第三个参数代表比较规则），没有第三个参数的时候，sort()默认按升序排列，有第三个参数的时候，可以通过这个参数实现各种各样的排序，包括降序。