如何上传网站,网站建设与管理大作业,网站设计的机构,做旅游那些网站好JAVA代码编写
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1#xff1a;
输入#xff1a;nums [-4,-1,0,3,10]
输出#xff1a;[0,1,9,16,100]
解释返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 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] 104nums 已按 非递减顺序 排序
进阶
请你设计时间复杂度为 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 left0;int rightnums.length-1;int knums.length-1;int[] resusltnew int[nums.length];//定义一个新的数组存放结果while(leftright){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, numsl1, ..., 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 1091 nums.length 1051 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 subLength0;//子序列的长度int resultInteger.MAX_VALUE;//将result定义为最大值int sum0;//子序列的和for (int i 0; i nums.length; i) {//子序列起始位置i下标sum0;//每次更新子序列起始位置就将子序列和置为0for (int j i; j nums.length; j) {//子序列结束位置j下标sumnums[j];//计算子序列的和if (targetsum ){subLengthj-i1;resultresultsubLength?result:subLength;//resultmin(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 left0;int resultInteger.MAX_VALUE;//将result定义为最大值int sum0;//子序列的和for(int right0;right nums.length; right){sumnums[right];while(sumtarget){result result(right-left1)?result:(right-left1);sum-nums[left];}}return result Integer.MAX_VALUE ? 0 : result;}
}这里还是以题目中的示例来举例s7 数组是 231243来看一下查找的过程
