代码随想录第二天继续数组相关题目
977. 有序数组的平方
一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
方法一
思路： 因为input数组已经是 非递减顺序， 所以平方后的最大值可能出现在这个数组的两侧。所以可以利用两个指针从input数组左右两侧开始取平方并比较，将其中较大的值放入output并移动指针，较小的停留在原地。如此从右向左依次填充output数组。
Time complexity: O(N)
Space complexity: O(1)
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int i = 0, j = n - 1, pos = n-1;
while(i <= j){
if( nums[i] * nums[i] >= nums[j] * nums[j] ){
res[pos--] = nums[i] * nums[i];
i++; //left++
} else{
res[pos--] = nums[j] * nums[j];
j--; //right--
}
}
return res;
}
}
方法二
对各个元素平方后，利用Arrays.sort() function 对数组进行排序。
trivial
Arrays.sort() function 时间复杂度 O(nlogn)
空间复杂度 O(logn) 因为使用logn空间的栈进行排序
In Java 8, Arrays.sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)). In short, TimSort makes use of the Insertion sort and the MergeSort algorithms.
Arrays.sort(primitives) uses a Dual-Pivot Quicksort algorithm. Its internal implementation from the JDK 10 is typically faster than traditional one-pivot Quicksort. It offers O(n log(n)) average time complexity
209. 长度最小的子数组
Medium
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
1. 暴力求解
利用两个 for 循环，一个 for 循环固定一个位置i，另一个 for 循环从 i 的下一个元素开始累加，当和大于等于 s 的时候终止内层循环，顺便记录下最小长度
时间复杂度 O(n*n)
空间复杂度：O(1)
提交超时
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
//因为要用来比较哪个值更小，所以初始为int Max_VALUE
int res = Integer.MAX_VALUE ;
for(int i = 0; i < nums.length; i++){
sum = nums[i];
if(sum >= target) return 1;
for(int j = i + 1; j < nums.length; j++){
sum += nums[j];
if(sum >= target){
res = Math.min(res, j - i + 1);
break; //因为要找符合条件最短的子序列，所以一旦符合条件就break
}
}
}
return res == Integer.MAX_VALUE ? 0 : res ;
}
}
2. 滑动窗口
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程.
滑动窗口则通过双指针分别指向起始位置与终止位置，通过一个for循环来完成
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动，如图所示：
在当前终止位置固定时， 找到满足sum >= target 的最短窗口。 然后再处理下一个终止位置
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0, left = 0; // sum为当前窗口数值之和； left为当前起始位置
int res = Integer.MAX_VALUE ;
for(int right = 0; right < nums.length; right++){ //right当前终止位置
sum += nums[right];
while(sum >= target){
sum -= nums[left];
res = Math.min(res, right - left + 1);
left++; //变更窗口起始位置
}
}
return res == Integer.MAX_VALUE ? 0 : res ;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
为什么时间复杂度是O(n)。
不要以为for里放一个while就以为是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。
59. 螺旋矩阵II
Medium难度
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路：
结果为 n * n 矩阵，模拟从1 到 n*n 螺旋状填充这个矩阵的过程
填充过程从左上角[1,1]开始,总是*顺序遵循以下四个方向：
- 自左向右填充当前最上行；
- 自上向下填充当前最右列；
- 从右向左填充当前最下行；
- 自下向上填充当前最左列；
可以定义四个变量来表示当前上，下，左，右 四个边界，每完成一个方向，更新相应的边界值。 例如从左到右填完后，上边界 top += 1，相当于上边界向内缩 1
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
//定义当前左右上下边界
int left = 0;
int right = n - 1;
int top = 0;
int buttom = n - 1;
int curr = 1; //填充起始值
int tar = n * n; //填充终止值， 也是需要填充的个数
while(curr <= tar){
//1.自左向右
for(int i = left; i <= right; i++){
res[top][i] = curr++; //先赋值，再increment
}
top++; //最上行处理完毕，top边界下移
//2.自上向下
for(int i = top; i <= buttom; i++){
res[i][right] = curr++;
}
right--; //最右列处理完毕，right边界左移
//3. 从右向左
for(int i = right; i >= left; i--){
res[buttom][i] = curr++;
}
buttom--; //最下行处理完毕，buttom边界上移
//4. 自下向上
for(int i = buttom; i >= top; i--){
res[i][left] = curr++;
}
left++; //最左列处理完毕，left边界右移
}
return res;
}
}
时间复杂度：O(n* n)
空间复杂度：O(n* n)
