代码随想录算法训练营Day1|704 二分查找，27移除元素

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;
};