【leetcode】力扣 --- 日积月累,每日一题——7 有序数组的平方
简单聊一下:临近期末了,一大堆论文接踵而至,今天写这个,明天写那个,突然发现今天的题还没刷。学习也还没有学习。昨天我导让我们开始看机器学习(西瓜书),兄弟们,如果有相关资源可以call我。I need you!!!
等 级 : 简 单 \textcolor{OrangeRed}{等级:简单} 等级:简单
我 之 前 提 交 了 几 遍 结 果 答 案 错 误 , 吃 了 个 饭 回 来 一 看 就 出 来 了 说 明 什 么 ? \textcolor{orange}{我之前提交了几遍结果答案错误,吃了个饭回来一看就出来了说明什么?} 我之前提交了几遍结果答案错误,吃了个饭回来一看就出来了说明什么?
说 明 饿 了 就 要 去 干 饭 , 否 则 代 谢 跟 不 上 \textcolor{red}{说明饿了就要去干饭,否则代谢跟不上} 说明饿了就要去干饭,否则代谢跟不上
一、题目
给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题
二、代码及思路
思路:这里看到和前面我做的题是有共同点的,做的题都是数组的,前面我们讲过一个双指针法
,【leetcode】力扣 — 日积月累,每日一题——6 移除元素。仔细一看这里也可以用得到,那就来试试。
仔细阅读题:整个数组是从小到大有序排列的,在它的基础上进行平方。根据数学知识我们可以知道,
在x轴上趋向两端无穷大。那么平方之后,数组的最大值要么在最前面,要么在在后面。我们使用一个双
指针法,一个指向最前端,一个指向最后端,往中间走。注意left=right的时候是有意义的。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] res = new int[nums.length];
int k = right;
while(left <= right){
if(nums[left] * nums[left] > nums[right] * nums[right]){
res[k] = nums[left] * nums[left];
left++;
k--;
}else{
res[k--] = nums[right] * nums[right];
right--;
}
}
return res;
}
}
相关文章
- Leetcode: Populating Next Right Pointers in Each Node II
- JS Leetcode 33. 搜索旋转排序数组题解,图解旋转数组中的二分法
- [LeetCode] Remove Duplicates from Sorted Array II
- 202、【数组】leetcode ——2588. 统计美丽子数组数目(C++版本)
- 173、【动态规划】leetcode ——300. 最长递增子序列 (C++版本)
- 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本)
- 116、【回溯算法】leetcode ——17. 电话号码的字母组合:回溯法:哈希映射+字符串数组映射(C++版本)
- 102、【树与二叉树】leetcode ——654. 最大二叉树(C++版本)
- 【LeetCode】42. Trapping Rain Water
- 【LeetCode】61. Rotate List
- LeetCode 26. 删除排序数组中的重复项
- [LeetCode] 1338. Reduce Array Size to The Half 数组大小减半
- [LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和
- [LeetCode] 1144. Decrease Elements To Make Array Zigzag 递减元素使数组呈锯齿状
- [LeetCode] 1031. Maximum Sum of Two Non-Overlapping Subarrays 两个不重叠的子数组的最大和
- [LeetCode] 974. Subarray Sums Divisible by K 子数组数字之和可被K整除
- [LeetCode] Minimum Distance Between BST Nodes 二叉搜索树中结点的最小距离
- [LeetCode] Binary Number with Alternating Bits 有交替位的二进制数
- [LeetCode] Map Sum Pairs 映射配对之和
- [LeetCode] Maximum Distance in Arrays 数组中的最大距离
- [LeetCode] 189. Rotate Array 旋转数组
- [LeetCode] 147. Insertion Sort List 链表插入排序
- leetcode 148. Sort List 排序链表(中等)