（二刷）代码随想录第1天|704. 二分查找 27. 移除元素

704. 二分查找

704. 二分查找 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

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

示例 1:
输入:
nums= [-1,0,3,5,9,12], 
target= 9
输出: 4
解释: 9 出现在 nums中并且下标为 4
示例 2:
输入:
nums= [-1,0,3,5,9,12], 
target= 2
输出: -1
解释: 2 不存在 nums中因此返回 -1
提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

使用二分法的前提条件：（第一反应还是没反应过来）

1、数组为有序数组

2、数组中无重复元素

⭐自己写的时候的2点疑惑：

1、while(left < right) 和while(left <= right) 哪个对？自己写的前者，运行超时

2、在更新左右边界的时候，到底是left=mid 还是left=mid+1?

果然卡哥就讲到了以上2点。

while(left < right) 还是while(left <= right)，取决于一开始你的区间选择是左闭右闭还是左闭右开。

两种选择都可以，我这里的选择是从头到尾区间都为左闭右闭区间。也就是[left,right]。注意：

1、这时候while(left <= right) 中的=不能掉，因为left=right是有意义的；

2、if(nums[mid] > target) right 要赋值为mid-1，因为在这之前已经判断出了mid的值不等于target, 那么mid的值就没必要再包含在要搜索的区间内了。

自己写的综合代码：

class Solution{public int search(int[] nums, int target){// 避免当 target 小于 nums[0] 或大于 nums[nums.length - 1] 时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1; // 如果目标值小于数组第一个元素或大于数组最后一个元素，则返回 -1}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){//更新左边界left = mid;}else if(nums[mid] > target){right = mid;}}return -1;        }}

leetcode上运行后：

询问chat超出时间限制的·原因：

改正后运行通过的代码：

class Solution{public int search(int[] nums, int target){// 避免当 target 小于 nums[0] 或大于 nums[nums.length - 1] 时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1; // 如果目标值小于数组第一个元素或大于数组最后一个元素，则返回 -1}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){//更新左边界left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}}return -1;        }}

27. 移除元素

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

第一反应是暴力解法。但是时间复杂度比较高：O(n^2)。

双指针法（快慢指针法）：
快慢指针代表的含义：

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组；

慢指针：指向更新新数组下标的位置。

综合代码：

class Solution{public int removeElement(int[] nums, int val){int slowIndex = 0;for(fastIndex = 0, fastIndex < nums.length, fastIndex++){if(nums[fastIndex] != val){slowIndex = fastIndex;slowIndex++;}}return slowIndex;}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/322247.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！