代码随想录算法——数组

目录

1、二分查找法

2、移除元素

3、有序数组的平方

4、长度最小的子数组

5、螺旋矩阵II

---

1、二分查找法

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int search (int[] nums, int target) {// write code hereint left=0;int right=nums.length-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}elseleft=mid+1;}return -1;}
}

2、移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素

class Solution {public int removeElement(int[] nums, int val) {int last=nums.length-1;// //自己想的方法// /*// 改变元素相对位置// 思想就是从头开始遍历，如果碰到val值就与数组后面的待检测值交换，// 交换后的值还可能是val，所以while继续交换，last用于保存待检测数组的最后边界// */// for(int i=0;i<=last;i++){      //     while(nums[i]==val&&last>=i){  //[2,3,2,3]  [3,3]//         nums[i]=nums[last];//         last=last-1;//     }// }// return last+1;/**这个别人的方法，也是改变元素位置*///  int leftIndex = 0;// int rightIndex = nums.length - 1;// while (leftIndex <= rightIndex) {//     // 找左边等于val的元素//     while (leftIndex <= rightIndex && nums[leftIndex] != val){//         ++leftIndex;//     }//     // 找右边不等于val的元素//     while (leftIndex <= rightIndex && nums[rightIndex] == val) {//         -- rightIndex;//     }//     // 将右边不等于val的元素覆盖左边等于val的元素//     if (leftIndex < rightIndex) {//         nums[leftIndex++] = nums[rightIndex--];//     }// }// return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素/*快慢指针方法我的理解就是慢指针相当于一个虚拟数组，当不等于val值，就存储fast数组的元素*/int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
}

3、有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

class Solution {public int[] sortedSquares(int[] nums) {/**数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。双指针法  i指向起始位置，j指向终止位置。前后依次遍历，定义一个新数组result，选择最大值从后往前填入新数组， */int i=0;int j=nums.length-1;int k=nums.length-1;int[] res=new int[nums.length];while(i<=j){if(nums[i]*nums[i]<=nums[j]*nums[j]){res[k--]=nums[j]*nums[j];j--;}else{res[k--]=nums[i]*nums[i];i++;}}return res;}
}

4、长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

• 输入：s = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

import java.util.*;
class Solution {public int minSubArrayLen(int target, int[] nums) {/**定义i,j快慢指针，找到最小连续数组，那么有起始位置和结束位置只有结束指针遍历了整个数组，所以可确定，i,j形成滑动窗口，窗口里面是满足和大于等于target值,固定结束指针，把起始指针往前移动，不满足和的条件再移动结束位置*/int sum=0;int minlen=Integer.MAX_VALUE;for(int i=0,j=0;j<nums.length;j++){sum+=nums[j];while(sum>=target){minlen=minlen>(j-i+1)?(j-i+1):minlen;sum-=nums[i];i++;}}return minlen==Integer.MAX_VALUE?0:minlen;}
}

5、螺旋矩阵II

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] 

class Solution {public int[][] generateMatrix(int n) {/**总共4条边，要遵循不变量原则,左闭右开这里n为奇数时，中间单独处理，最大的数*/int res[][]=new int[n][n];int a=1;int i=0,j=0;int x=0;//x是循环的次数，也是用于边界限定的int aa=n*n+1;if(n%2!=0){aa-=1;}while(a<aa){//从左到右，for(;j<n-1-x;j++){//每一圈循环边界减少1res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从上到下for(;i<n-1-x;i++){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从右到左    for(;j>0+x;j--){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}//从下到上for(;i>0+x;i--){res[i][j]=a;System.out.println(i+" "+j+" ="+a);a++;}x++;//x是作为圈数，也是边界减少的数量i=x;//这里定义ij为每次循环的起点，都是 00 11 22 33因此和x相同j=x;}if(n%2!=0){res[n/2][n/2]=a;}return res;}
}