704.给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
提示:
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
二分法的前提条件:
1.有序的,（升序）的数组
2.所有元素是不重复的
二分法容易在边界条件的判断上出错 ,在何时使用while(left 方法一: 保证target一直在一个左闭右闭的区间[left,right]: 1.left=0,right=nusm.length-1; 2.使用while(left<=right) 因为nums[left]可能是target,nums[right]也可能是target,目的是保证target一直在一个左闭右闭的区间[left,right] 3.使用left=mid+1和 mid=right-1 因为当nums[mid] target一定不等于nums[mid],我们要保证保证target一直在一个左闭右闭的区间,所以left=mid+1 同里可知:nums[mid]>target时,mid=right-1 出现超出时间的提示可能就是这里没有加减1 例如这题如果写成left=mid,mid=right 就会一直在[2,3]区间之间判断,陷入死循环 参考代码: class Solution { public int search(int[] nums, int target) { int start=0; int end=nums.length-1; int mid; while(start<=end){ mid=(start+end)/2; if(nums[mid]>target){ end=mid-1; }else if(nums[mid] start=mid+1; }else{ return mid; } } return -1; } } 方法二: while(left<=right) 1left=0,right=nusm.length: nums[right]一定不为target,为了保证target 是在一个在左闭右开的区间[left,right) 2 while(left 我们保证target 一直是在一个在左闭右开的区间[left,right),所以当left=right时,一定是没有找到target,这时我们退出循环 3使用left=mid+1和 mid=right 当nums[mid]>target时: nums[mid]!=target,我们保证target 一直是在一个在左闭右开的区间[left,right),所以使用right=mid 当nums[mid] nums[mid]!=target,我们保证target 一直是在一个在左闭右开的区间[left,right),所以使用left=mid+1 参考代码: class Solution { public int search(int[] nums, int target) { int start=0; int end=nums.length; int mid; while(start mid=(start+end)/2; if(nums[mid]>target){ end=mid; }else if(nums[mid] start=mid+1; }else{ return mid; } } return -1; } } 分割线 27. 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。 方法1: 暴力法 我们使用两层for循环,一层遍历数组,找到要删除的值,另一层执行把后往前的覆盖 这里需要注意的两点是 1.j 2.i--,我们覆盖后,相当于i已经指向下一位了,所以要在i自增前先减1 class Solution { public int removeElement(int[] nums, int val) { int size=nums.length; for(int i=0;i if(nums[i]==val){ for(int j=i;j nums[j]=nums[j+1]; } size--; i--; } } return size; } } 方法二: 双指针法 快指针:遍历数组所有的数,找到目标数 慢指针:更新新数组的值 步骤: 当快指针指向目标值时,只有快指针前进一步 当快指针不是指向目标值时,将快指针指向的值赋给慢指针指向的位置,快慢指针同时前进一步 参考代码 class Solution { public int removeElement(int[] nums, int val) { int slow=0; int fast=0; while(fast if(nums[fast]==val){ fast++; }else{ nums[slow++]=nums[fast++]; } } return slow; } } 时间复杂度：O(n)空间复杂度：O(1) 方法3: 双向指针 : 本题中元素的顺序可以改变: class Solution { public int removeElement(int[] nums, int val) { int left = 0; int right = nums.length - 1; while (left <= right) { while (left <= right && nums[left] != val) { left++; //找到左边第一个为val的数 } while (left <= right && nums[right] == val) { right--;找到右边第一个不为val的数 } if (left < right) { nums[left++] = nums[right--];//交换 } } return left; } 如有任何问题,欢迎留言 相关文章
您阅读本篇文章共花了：
发表评论