暗暗那的个人博客

代码随想录

https://programmercarl.com/0027.移除元素.html

题目

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

笔记

暴力实现

双重for循环，先遍历数组，遇到要删的元素就再遍历后面的每一个元素，并把它们向前移一位。
时间复杂度是O(n^2)，空间复杂度是O(1)。

数组方法

C++中有一个库函数叫array.erase()，可以直接删除数组中的元素，即把该元素后面的所有元素都往前提一位，时间复杂度是O(n)。
js中没有直接删除的库函数，js实现删除数组元素有以下几种方法：

1. filter()

   1	array.filter(item => item !== valToRemove)

2. for循环 + array.splice

   1 2 3 4 5

   for (let idx = arr.length - 1; idx >= 0; idx --) { if (arr[idx] === valToRemove) { arr.splice(idx, 1); } }

3. splice() + indexOf()
   这个方法只能删除数组中第一个等于valToRemove的元素。

   1 2	const idx = arr.indexOf(valToRemove); arr.splice(idx, 1);

在本题中，我最开始的思路是filter() + forEach()，先用filter剔除不需要的元素，再把剔除后的新数组的元素逐个复制粘贴到原数组。
时间复杂度O(n)，空间复杂度O(n)。

1
2
3
4
5
6
7

var removeElement = function(nums, val) {
    const valArr = nums.filter(item => item !== val);
    valArr.forEach((_, idx) => {
        nums[idx] = valArr[idx];
    });
    return valArr.length;
};

双指针法（快慢指针法）

一个快指针和一个慢指针同时从数组的索引0出发，首先快指针开始一个一个地往后走，当快指针遇到要保留的元素且快指针与慢指针不在同一处时，把快指针的值赋给慢指针处，并让慢支针往后走一位。重复操作，直到快指针走到arr.length。
时间复杂度O(n)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9

var removeElement = function(nums, val) {
    let slow = 0;
    for (let fast = 0; fast < nums.length; fast ++) {
        if (nums[fast] !== val) {
            nums[slow ++] = nums[fast];
        }
    }
    return slow;
};

代码随想录

https://programmercarl.com/0704.二分查找.html#算法公开课

题目

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

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

笔记

什么是二分法？
在一个有序序列中找一个目标数target，先把数组一分为二，看target比数组的中点数大还是小，来判断target在数组的右半边还是左半边。假如在左半边，就再把左半边一分为二来找，直到找到target或找完整个数组。每次框定区间时，left指向数组在区间中国呢的最左边索引，right指向最右边索引，middle指向中点索引，若中点索引不是整数，则middle取小于且最接近中点索引的整数。

实际编写二分法的三个易错点：

1. 一开始right应该取arr.length还是arr.length - 1？
2. 循环继续的条件是left < right还是left <= right
3. 循环中移动right时，是移到middle，还是middle - 1？移动left呢？

这几个问题取决于我们在搜索过程中对于取值区间的定义，是左闭右开[left,right)，还是左闭右闭[left,right]。

若对区间的定义是左闭右闭，则：

• 一开始取的left和right要满足[left, right]能包含数组中的所有值，所以可以取left=0，right=arr.length - 1
• 当left===right时，[left,right]也是合法的区间，也是需要被查找的，所以要等到left < tight才能确定数组里找不到target。
• 当arr[mid] > targer时，就确定了mid位置没有target，而[left,mid]包括mid，所以right应该移到mid - 1处。
• 当arr[mid] < targer时，[mid,right]包括mid，所以right应该移到mid - 1处。

若对区间的定义是左闭右开，则：

• 一开始取的left和right要满足[left, right)能包含数组中的所有值，所以可以取left=0，right=arr.length
• 当left===right时，[left,right)不是合法的区间，所以除了left < tight能确定找不到，left = tight也能。
• 当arr[mid] > targer时，就确定了mid位置没有target，而[left,mid)不包括mid，所以right移到mid处就行。
• 当arr[mid] < targer时，[mid,right)包括mid，所以right应该移到mid - 1处。这一点和左闭右闭是一样的。

左闭右闭版

我个人比较喜欢左闭右闭，不用考虑哪里是开区间哪里是闭区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

const search = (arr, target) => {
    let l = 0, r = arr.length - 1, mid;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (target < arr[mid]) {
            r = mid - 1;
        } else if (target > arr[mid]) {
            l = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

左闭右开版

若一开始r取了arr.length - 1，就会在search([3], 3)时翻车。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

const search = (arr, target) => {
    let l = 0, r = arr.length, mid;// 区别1
    while (l < r) { // 区别2
        mid = l + ((r - l) >> 1);
        if (target < arr[mid]) {
            r = mid; // 区别3
        } else if (target > arr[mid]) {
            l = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

自我摸索版

在只知道基本原理，还没看讲解时，我自己在力扣写了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    const func = () => {
        if (left > right) {
            return -1;
        }
        const mid = left + Math.floor((right - left) / 2);
        if (target > nums[mid]) {
            left = mid + 1;
            return func();
        } else if (target < nums[mid]) {
            right = mid - 1;
            return func();
        } else {
            return mid;
        }
    }
    return func();
};

遇到的问题有：

1. 没想到用while就行，为了做到循环还写出来了一个递归函数
2. 没想过我定义的区间是左闭右闭还是左闭右开，导致一边写left > right时才停止，一边写right会移到mid。
3. 查了一下怎么向下取整，查到可以用Math.floor()
4. 取a和b的平均值(a < b)时，可以用(b + a)/2，我当时只能的a + (b - a)/2。但是之后看了代码随想录的解答，人家也是用的小数加上二者的差，因为这样能预防两数相加时大数溢出。
5. 我想实现a/2并忽略小数部份，写的是Math.floor(a/2)，而代码随想录用的是a >> 1。在JavaScript里，>>1 是位运算符中的右移一位操作‌。如果对一个整数 x 使用 x >> 1，则相当于将 x 除以2并向下取整（对于正数和0）或向上取整后取相反数（对于负数）。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment