网页设计实验报告精品课程网站,如何建设cpa影视网站,流程图制作网页,帝国网站搬家教程文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;有序数组的平方
出处#xff1a;977. 有序数组的平方
难度
2 级
题目描述
要求
给定按非递减顺序排序的整… 文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题有序数组的平方
出处977. 有序数组的平方
难度
2 级
题目描述
要求
给定按非递减顺序排序的整数数组 nums \texttt{nums} nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。
示例
示例 1
输入 nums [-4,-1,0,3,10] \texttt{nums [-4,-1,0,3,10]} nums [-4,-1,0,3,10] 输出 [0,1,9,16,100] \texttt{[0,1,9,16,100]} [0,1,9,16,100] 解释平方后数组变为 [16,1,0,9,100] \texttt{[16,1,0,9,100]} [16,1,0,9,100]。排序后数组变为 [0,1,9,16,100] \texttt{[0,1,9,16,100]} [0,1,9,16,100]。
示例 2
输入 nums [-7,-3,2,3,11] \texttt{nums [-7,-3,2,3,11]} nums [-7,-3,2,3,11] 输出 [4,9,9,49,121] \texttt{[4,9,9,49,121]} [4,9,9,49,121]
数据范围 1 ≤ nums.length ≤ 10 4 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{4} 1≤nums.length≤104 -10 4 ≤ nums[i] ≤ 10 4 \texttt{-10}^\texttt{4} \le \texttt{nums[i]} \le \texttt{10}^\texttt{4} -104≤nums[i]≤104 nums \texttt{nums} nums 已按非递减顺序排序
进阶
计算每个元素的平方并对新数组排序的解法很简单你可以使用不同的方法找到时间复杂度 O(n) \texttt{O(n)} O(n) 的解法吗
解法一
思路和算法
最直观的解法是依次计算数组 nums \textit{nums} nums 中的每个元素的平方并存入新数组中然后对新数组按非递减顺序排序即可得到排序后的新数组。
代码
class Solution {public int[] sortedSquares(int[] nums) {int length nums.length;int[] squares new int[length];for (int i 0; i length; i) {squares[i] nums[i] * nums[i];}Arrays.sort(squares);return squares;}
}复杂度分析 时间复杂度 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 是数组 nums \textit{nums} nums 的长度。计算数组 nums \textit{nums} nums 中的每个元素的平方并存入新数组需要 O ( n ) O(n) O(n) 的时间对新数组排序需要 O ( n log n ) O(n \log n) O(nlogn) 的时间因此时间复杂度是 O ( n log n ) O(n \log n) O(nlogn)。 空间复杂度 O ( log n ) O(\log n) O(logn)其中 n n n 是数组 nums \textit{nums} nums 的长度。对新数组排序需要 O ( log n ) O(\log n) O(logn) 的递归调用栈空间。注意返回值不计入空间复杂度。
解法二
思路和算法
解法一没有利用到数组 nums \textit{nums} nums 已经按非递减顺序排序的条件因此需要对新数组排序时间复杂度是 O ( n log n ) O(n \log n) O(nlogn)。如果利用数组 nums \textit{nums} nums 已经按非递减顺序排序的条件则不需要对新数组排序将时间复杂度降低到 O ( n ) O(n) O(n)。
由于一个数的平方大小与这个数的绝对值有关因此考虑数组 nums \textit{nums} nums 中的绝对值最大元素与绝对值最小元素可能出现的位置。
数组 nums \textit{nums} nums 按非递减顺序排序可能有以下三种情况 数组 nums \textit{nums} nums 的所有元素都是非负数元素顺序为绝对值非递减顺序首个元素的绝对值最小末尾元素的绝对值最大 数组 nums \textit{nums} nums 的所有元素都是非正数元素顺序为绝对值非递增顺序首个元素的绝对值最大末尾元素的绝对值最小 数组 nums \textit{nums} nums 中既有正数也有负数首个元素或末尾元素的绝对值最大。
对于上述三种情况中的任意一种情况绝对值最大的元素一定是数组 nums \textit{nums} nums 的首个元素或末尾元素。因此可以从数组 nums \textit{nums} nums 的两端向中间遍历按照绝对值从大到小的顺序依次遍历数组 nums \textit{nums} nums 的元素计算每个元素的平方反向填入新数组。
具体做法是维护两个下标 index 1 \textit{index}_1 index1 和 index 2 \textit{index}_2 index2初始时 index 1 \textit{index}_1 index1 指向数组 nums \textit{nums} nums 的首个元素 index 2 \textit{index}_2 index2 指向数组 nums \textit{nums} nums 的末尾元素。遍历过程中比较 nums [ index 1 ] \textit{nums}[\textit{index}_1] nums[index1] 和 nums [ index 2 ] \textit{nums}[\textit{index}_2] nums[index2] 这两个元素的绝对值 如果 nums [ index 1 ] \textit{nums}[\textit{index}_1] nums[index1] 的绝对值大于 nums [ index 2 ] \textit{nums}[\textit{index}_2] nums[index2] 的绝对值则将 nums [ index 1 ] \textit{nums}[\textit{index}_1] nums[index1] 的平方填入新数组将 index 1 \textit{index}_1 index1 加 1 1 1 如果 nums [ index 1 ] \textit{nums}[\textit{index}_1] nums[index1] 的绝对值小于等于 nums [ index 2 ] \textit{nums}[\textit{index}_2] nums[index2] 的绝对值则将 nums [ index 2 ] \textit{nums}[\textit{index}_2] nums[index2] 的平方填入新数组将 index 2 \textit{index}_2 index2 减 1 1 1。
由于遍历数组 nums \textit{nums} nums 的过程中每次遍历的元素都是尚未遍历的元素中的绝对值最大的元素因此遍历元素的顺序是绝对值非递增顺序即元素的平方非递增顺序。将遍历的元素的平方反向填入新数组新数组中的元素顺序为非递减顺序。
代码
class Solution {public int[] sortedSquares(int[] nums) {int length nums.length;int[] squares new int[length];int index1 0, index2 length - 1;for (int i length - 1; i 0; i--) {if (Math.abs(nums[index1]) Math.abs(nums[index2])) {squares[i] nums[index1] * nums[index1];index1;} else {squares[i] nums[index2] * nums[index2];index2--;}}return squares;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 中的每个元素一次。 空间复杂度 O ( 1 ) O(1) O(1)。注意返回值不计入空间复杂度。
