704.二分查找
题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
文章讲解：代码随想录
视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找
过程：区间定义不清晰
知识点
- 使用二分法的前提条件：有序数组且无重复元素
- 区间定义一般分为两种：左闭右闭即[left,right] 或 左闭右开即[left, right)
实现一
定义目标值target是左闭右闭[left,right]中的，所以结束条件为left<=right
注意：初始化right=nums.length - 1，不然会出现数组越界情况
比如：nums=[-1,0,3,5,9,12], target=13，当right=nums.length时
以下代码console结果为：
0 6 3
4 6 5
6 6 6
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while(left <= right) {
let middle = Math.floor((left + right) / 2)
console.log(left, right, middle)
if (nums[middle] > target) { // 说明target在左区间内
right = middle - 1;
} else if (nums[middle] < target) { // 说明target在右区间内
left = middle + 1;
} else { // 找到target，返回对应下标
return middle;
}
}
return -1;
};
实现二
定义目标值target是左闭右开[left,right)中的，所以结束条件为left<right
注意：初始化right=nums.length
比如：nums=[5], target=5，当right=nums.length - 1时，会缺少比较情况，导致结果错误
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
var search = function(nums, target) {
let left = 0;
let right = nums.length;
while(left < right) {
let middle = Math.floor((left + right) / 2)
if (nums[middle] > target) { // 说明target在左区间[left, middle)内
right = middle;
} else if (nums[middle] < target) {// 说明target在左区间[middle+1, right)内
left = middle + 1;
} else if (nums[middle] === target) {// 找到target，返回对应下标
return middle;
}
}
return -1;
};
27.移除元素
题目描述：
给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用O(1)额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
文章讲解：代码随想录
视频讲解：数组中移除元素并不容易！LeetCode：27. 移除元素
实现一：暴力解法
思路： 双重for循环，第i层循环负责循环nums，依次比较val，第j层循环负责找到目标值，依次移动j后面的每一个元素
注意：每进行1次移动后，要删除末尾元素，因为在赋值过程中，没有处理nums[j]，所以数组的长度并没有发生变化
举例：nums=[0,1,2,2,3,0,4,2]， val=2
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
var removeElement = function(nums, val) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === val) {
for(let j = i + 1; j < nums.length; j++) {
nums[j - 1] = nums[j]
}
nums.pop()
i--;
}
}
};
实现二：双指针法
双指针(快慢指针法)：通过一个快指针，一个慢指针，在一个for循环里完成两个for循环的工作
定义快慢指针：
- 快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
思路：快慢指针同时移动，只保留赋值快指针中不等于目标值的元素
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
var removeElement = function(nums, val) {
let slowIndex = 0;
for (let fastIndex = 0; fastIndex < nums.length; fastIndex++) {
if (nums[fastIndex] !== val) {
nums[slowIndex++] = nums[fastIndex]
}
}
return slowIndex;
};
由于题目已经说明不需要考虑数组中超出新长度后面的元素，因此只需返回满足条件后数组的长度即可，如果想得到更新后的数组，可以参考以下代码：
var removeElement = function(nums, val) {
let slowIndex = 0;
for (let fastIndex = 0; fastIndex < nums.length;) {
if (nums[fastIndex] !== val) {
nums[slowIndex] = nums[fastIndex]
slowIndex++
fastIndex++
} else {
nums.splice(slowIndex, 1)
}
}
return nums.length;
};
