海南省住房和城乡建设官方网站,商丘58同城招聘网最新招聘,爱狼戈网站建设,镇江推广公司代码随想录——数组篇 2. 二分查找3. 移除元素4. 有序数组的平方5. 长度最小的子数组6. 螺旋矩阵II 2. 二分查找
力扣题目链接
前提#xff1a;
有序数组数组中无重复元素
代码#xff1a;
#xff08;版本一#xff09;左闭右闭区间
class Solution {public int sea… 代码随想录——数组篇 2. 二分查找3. 移除元素4. 有序数组的平方5. 长度最小的子数组6. 螺旋矩阵II 2. 二分查找
力扣题目链接
前提
有序数组数组中无重复元素
代码
版本一左闭右闭区间
class Solution {public int search(int[] nums, int target) {//当 target 小于nums的最小值 或 大于nums的最大值时直接返回-1if(target nums[0] || target nums[nums.length - 1])return -1;int left 0, right nums.length - 1, mid;while(left right) {mid left ((right- left) 1);if(nums[mid] target)return mid;else if(nums[mid] target)right mid - 1;elseleft mid 1;}return -1;}
}时间复杂度O(log n)空间复杂度O(1)
版本二左闭右开区间
class Solution {public int search(int[] nums, int target) {//当 target 小于nums的最小值 或 大于nums的最大值时直接返回-1if(target nums[0] || target nums[nums.length - 2])return -1;int left 0, right nums.length - 1, mid;while(left right) {mid left ((right- left) 1);if(nums[mid] target)return mid;else if(nums[mid] target)right mid;elseleft mid 1;}return -1;}
}时间复杂度O(log n)空间复杂度O(1)
3. 移除元素
力扣题目链接
代码
双指针法快慢指针法
class Solution {public int removeElement(int[] nums, int val) {int j 0;for(int i 0; i nums.length; i) {if(nums[i] ! val) {nums[j] nums[i];}} return j;}
}时间复杂度O(n)空间复杂度O(1)
4. 有序数组的平方
力扣题目链接
前提
非递减顺序 排序的整数数组
思路 数组本身有序平方和较大的值一定出现在两端可以借用前面学习的双指针法。
代码
class Solution {public int[] sortedSquares(int[] nums) {int[] result new int[nums.length];int left 0, right nums.length - 1, index nums.length - 1;while(left right) {if(nums[left] * nums[left] nums[right] * nums[right]) {//大的值从后往前放result[index--] nums[right] * nums[right];right - 1;}else {result[index--] nums[left] * nums[left];left 1;}}return result;}
}时间复杂度O(n)空间复杂度O(n)
5. 长度最小的子数组
力扣题目链接
滑动窗口 不断调节子序列的起始位置和终止位置从而得出想要的结果。
滑动窗口三要素
窗口内是什么 满足其和 ≥ target 的长度最小的 连续 子数组。 如何移动窗口的起始位置 如果当前窗口的值 ≥ target 了窗口就要向前移动了窗口该缩小了。 如何移动窗口的结束位置 窗口的结束位置就是遍历数组的指针也就是for循环里的索引。
代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0, sum 0, result Integer.MAX_VALUE;for (int right 0; right nums.length; right) {sum nums[right];//如果滑动窗口内的总和大于或等于targetwhile(sum target) {//更新最小子序列长度result Math.min(result, right - left 1);//移动滑动窗口的起始位置缩小窗口sum - nums[left];}}return result Integer.MAX_VALUE ? 0 : result;}
}时间复杂度O(n)空间复杂度O(1)
6. 螺旋矩阵II
力扣题目链接
代码
class Solution {public static int[][] generateMatrix(int n) {//定义起始x, y, 偏移量offsetint startX 0, startY 0, offset 1;//定义移动指针i, j, 圈数loop, 数字numint i, j, loop n 1, num 1;//定义n * n的矩阵int[][] arr new int[n][n];//模拟循环while((loop--) 0) {//从左到右左闭右开for (j startY; j n - offset; j) {arr[startX][j] num;}//从上到下左闭右开for (i startX; i n - offset; i) {arr[i][j] num;}//从右到左左闭右开for ( ; j startY; j--) {arr[i][j] num;}//从下到上左闭右开for ( ; i startX; i--) {arr[i][j] num;}//一圈结束起始位置1如(0, 0) 变为(1, 1)startX;startY;//offset同步更新offset;}//如果n为奇数中间的数单独赋值if(n % 2 1)arr[startX][startY] num;return arr;}
}时间复杂度O(n^2)空间复杂度O(1)
