代码随想录算法——数组
目录
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 here
int 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;
}
else
left=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++){//每一圈循环边界减少1
res[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;
}
}