leetcode-01-[704]二分查找[27]移除元素

一、[704]二分查找

//二分法：有序 //[left,right] 故判定条件为left <= right,等于此时有意义； //缩小范围 left=mid+1； //right= nums.length-1; //不要忘了修改mid 的值 class Solution { public int search(int[] nums, int target) { int left=0; int right= nums.length-1; int mid=(right+left)/2; while(left<=right) { if(nums[mid]>target){ right=mid-1; } else if (nums[mid]<target) { left=mid+1; }else{ return mid; } mid=(right+left)/2;//不要忘了修改mid 的值 } return -1; } }

一些注意事项

1、核心思想：排除不符合条件的区间

2、区间

普通查找：左闭右闭区间

找边界：左闭右开区间

3、普通二分查找

可以理解为找>=target的第一个元素，left的含义为第一个满足条件的元素，right为最后一个不满足条件的元素

4、找边界

left=mid+1;

right=mid 或mid-1 ，主要看此时mid是不是候选值，虽然mid在上一轮已经检查过，但也可能满足条件（特殊的，左闭右开区间，right=mid，因为此时是开区间，mid已排除；反之若right=mid-1,则排除了mid-1这个元素）

二、[27]移除元素

1、对撞指针

改变了元素的相对顺序

class Solution { public int removeElement(int[] nums, int val) { int left=0,right= nums.length-1; while(left<=right) { if(nums[left]!=val&&nums[right]==val) { left++; right--; }else if(nums[left]!=val&&nums[right]!=val){ left++; } else if (nums[left]==val&&nums[right]==val) { right--; } else if (nums[left]==val&&nums[right]!=val) { int tmp=nums[left]; nums[left]=nums[right]; nums[right]=tmp; left++; right--; } } return left; } }

2、对撞指针代码优化

class Solution { public int removeElement(int[] nums, int val) { int left = 0; int right = nums.length - 1; while (left <= right) { if (nums[left] != val) { left++; } else if (nums[right] == val) { right--; } else { nums[left] = nums[right]; right--; } } return left; } }

3、快慢指针（推荐）

没有改变元素的相对顺序

//快指针：找到与目标值不相同的值，将其传给慢指针 //慢指针：接收快指针的值 class Solution { public int removeElement(int[] nums, int val) { // 快慢指针 int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { if (nums[fastIndex] != val) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } } return slowIndex; } }