JAVA代码编写
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 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)
的算法解决本问题
文章讲解:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解: https://www.bilibili.com/video/BV1QB4y1D7ep
方法一:暴力排序
思路:遍历数组中的元素,算出平方和,再调用函数排序即可。
复杂度分析:取决于排序的复杂度
- 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
class Solution {
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i]*=nums[i];
}
Arrays.sort(nums);
return nums;
}
}
方法二:双指针法
思路:因为输入的数组是递增的,平方操作后的最大值只可能在数组两边,此时,只需要比较两边的数,找到最大的数,依次进行比较。
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
class Solution {
public int[] sortedSquares(int[] nums) {
int left=0;
int right=nums.length-1;
int k=nums.length-1;
int[] resuslt=new int[nums.length];//定义一个新的数组,存放结果
while(left<=right){
if(nums[left]*nums[left] > nums[right]*nums[right]){
resuslt[k]=nums[left]* nums[left];//result[k]赋值为较大的值
k--;//result[k]赋值完后,k要相对于减一进行下一次赋值
left++;//左指针右移
}else{
resuslt[k]=nums[right]*nums[right];
k--;
right--;//右指针左移
}
}
return resuslt;
}
}
其他写法:
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = result.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
// 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置
result[index--] = nums[left] * nums[left];
++left;
} else {
result[index--] = nums[right] * nums[right];
--right;
}
}
return result;
}
}
class Solution {
public int[] sortedSquares(int[] nums) {
int l = 0;
int r = nums.length - 1;
int[] res = new int[nums.length];
int j = nums.length - 1;
while(l <= r){
if(nums[l] * nums[l] > nums[r] * nums[r]){
res[j--] = nums[l] * nums[l++];
}else{
res[j--] = nums[r] * nums[r--];
}
}
return res;
}
}
这两个写法,只是在++和–上有简化代码作用,使得代码更为简洁。
209. 长度最小的子数组
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度**。**如果不存在符合条件的子数组,返回 0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)
时间复杂度的解法, 请尝试设计一个O(n log(n))
时间复杂度的解法。
文章讲解:https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解:https://www.bilibili.com/video/BV1tZ4y1q7XE
方法一:暴力解法
思路:两层for循环,第一层表示子序列的起始位置,第二层表示子序列的结束位置,计算子序列起始位置到终止位置的和sum,如何和sum大于等于target,就计算当前子序列的长度,与初始长度,比较,找最小的长度。找不到的话返回0。
复杂度分析:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int subLength=0;//子序列的长度
int result=Integer.MAX_VALUE;//将result定义为最大值
int sum=0;//子序列的和
for (int i = 0; i < nums.length; i++) {//子序列起始位置i(下标)
sum=0;//每次更新子序列起始位置,就将子序列和置为0
for (int j = i; j < nums.length; j++) {//子序列结束位置j(下标)
sum+=nums[j];//计算子序列的和
if (target<=sum ){
subLength=j-i+1;
result=result<subLength?result:subLength;//result=min(subLength,result)
break;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;//result没有被赋值,就说明不存在这样的子序列,返回0
}
}
方法二:滑动窗口
思路:用一个循环干方法一的事,方法一是从子序列的起始位置开始变量的,这里我们从子序列的结束位置开始往前遍历。
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left=0;
int result=Integer.MAX_VALUE;//将result定义为最大值
int sum=0;//子序列的和
for(int right=0;right < nums.length; right++){
sum+=nums[right];
while(sum>=target){
result= result<(right-left+1)?result:(right-left+1);
sum-=nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程: