目录
704. 二分查找
分类:
左闭右闭、左闭右开
Tips:
1.循环条件:
左闭右闭:左索引<=右索引
左闭右开:左索引<右索引
2.循环操作:
处理元素>目标值:
左闭右闭:右索引=折半索引-1
左闭右开:右索引=折半索引
class Solution {
public int search(int[] nums, int target) {
int n=nums.length;
int leftindex=0;
int rightindex=n-1;
while(leftindex<=rightindex){
int midindex=(leftindex+rightindex)/2;
if(nums[midindex]==target){
return midindex;
} else if(nums[midindex]<target){
leftindex=midindex+1;
}else{
rightindex=midindex-1;
}
}
return -1;
}
}
27. 移除元素
Tips:
双指针:
左索引——>被赋值元素
右索引——>当前处理元素
class Solution {
public int removeElement(int[] nums, int val) {
int n=nums.length;
int leftindex=0;
for(int rightindex=0;rightindex<n;rightindex++){
if(nums[rightindex]!=val){
nums[leftindex]=nums[rightindex];
leftindex++;
}
}
return leftindex;
}
}
977.有序数组的平方
Tips:
循环条件:
左索引<=右索引
双指针(利用数组从两端到中间有序的特点)
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
int leftindex=0;
int rightindex=n-1;
int [] newnums=new int[n];
int assignindex=n-1;
while(leftindex<=rightindex){
if(nums[leftindex]*nums[leftindex]>nums[rightindex]*nums[rightindex]){
newnums[assignindex]=nums[leftindex]*nums[leftindex];
leftindex++;
assignindex--;
}else{
newnums[assignindex]=nums[rightindex]*nums[rightindex];
rightindex--;
assignindex--;
}
}
return newnums;
}
}