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

2023-11-20 22:52

本文主要是介绍LeetCode977.有序数组的平方(双指针法、暴力法、列表推导式),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode977.有序数组的平方

  • 1.问题描述
  • 2.解题思路
  • 3.代码
  • 4.知识点

1.问题描述

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

示例 1:

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

示例 2:

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

提示:

  • 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 Listclass Solution:def sortedSquares(self, nums: List[int]) -> List[int]:k = len(nums) - 1# 创建一个与输入列表长度相等的列表,用于存储结果res = [0] * len(nums)# 定义两个指针 i 和 j,分别指向列表的首尾i, j = 0, len(nums) - 1while i <= j:# 如果左边指针的平方大于右边指针的平方if nums[i] ** 2 > nums[j] ** 2:# 将左边指针的平方存入结果列表的末尾res[k] = nums[i] ** 2# 左边指针向右移动一位i += 1else:# 将右边指针的平方存入结果列表的末尾res[k] = nums[j] ** 2# 右边指针向左移动一位j -= 1# 结果列表的索引向前移动一位k -= 1# 返回结果列表return resarr = [-5, 3, 3, 4]
# 创建Solution类的实例
solution = Solution()
result = solution.sortedSquares(arr)
print(result)

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

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

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

C++:双指针法

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;// 定义一个大小为原数组大小的,元素全部为 0 的新数组 resvector<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;
}

C++:暴力法

#include <iostream>
#include <vector>
#include <algorithm>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;
}

4.知识点

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

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

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

    def function_name(parameters: type) -> return_type:# 函数体return value
    
  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()默认按升序排列,有第三个参数的时候,可以通过这个参数实现各种各样的排序,包括降序。

这篇关于LeetCode977.有序数组的平方(双指针法、暴力法、列表推导式)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/398027

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

Spring+MyBatis+jeasyui 功能树列表

java代码@EnablePaging@RequestMapping(value = "/queryFunctionList.html")@ResponseBodypublic Map<String, Object> queryFunctionList() {String parentId = "";List<FunctionDisplay> tables = query(parent

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou