1.数组理论基础

文章地址

1.1 一维数组

要先理解数组在内存中的存储方式：
数组是存放在连续内存空间上的相同类型数据集合

可以通过下标索引获取该索引对应数据。
因为数组内存空间的地址连续，所以删除或增加元素必然影响到其他元素，需要移动其他元素的地址

但是数组元素不能删除，只能覆盖

数组如果不用的话也不用删除操作，而是赋值为null（js）从而释放对原数组的引用,js的垃圾回收机制让他在适当时候清理占用的内存

1.1 二维数组

二维数组

在js中二维数组在内存中的地址不连续，是分散存储在各自一维数组的内存地址中。

let array = [
  [1,2,3],
  [4,5,6]
];

2. leetcode 704 二分查找

题目链接

视频讲解

2.1二分法介绍

前提：必须是有序的数据集合，通常升序。以及，如果要查找元素，数据集合应该没有重复元素，不然返回的下标可能不唯一。
初始化：左右边界和要查找的目标元素
取中间元素
比较

2.2 思路

重点是要确定区间，并且一直保持不变量。
有两种区间设定方法：

[ XX ]左闭右闭

[ XX )左闭右开

2.3 右开注意事项：

right一开始的赋值就是length，因为取不到
let right = nums.length
while的判断没有等于，因为不可能等于，右边取不到
mddile赋值给left的话要用middle+1,因为middle已经发现不是了，

该思路碰到的问题：

取中位数不会位运算

一开始用的
```
let middle = (left+right)/2;
```
实在太慢了，因为用了浮点数除法和取整，
而在计算机中位运算是整数运算，

右移位运算（5 >> 1）:先转成2进制，右移一位，移出去的舍弃，左边补0，如果是负数换成补码进行移位，左边补1，

不管正负数，m右移n位就是m/2ⁿ

middle没有在循环内重新赋值，导致出错
```
 let mid,left =0;
```
写成了
```
let left,mid = 0;
```
导致的结果就是，以为left和mid都赋值了，但是comma前面的只是declared了，但是没有assign a value to it.
(right-left) >> 1没有一起包起来导致超时，

2.4 拓展题目

35.搜索插入位置

34.在排序数组中查找元素的第一个和最后一个位置

3.leetcode 27 移除元素

文章地址

3.1思路：

思路1:暴力破解（两个for一个负责看是不是该值；如果是该值，另一个负责全部前移一位）
注意事项：
1. 数组的大小一直是固定的，因为数组元素不能删除，我们只是覆盖了取了新的长度（看动画）
2. 内部for的参数j的取值：
  一开始我取的:
```
for(let j =i;j<length -i-1;j++){
    nums[j+1] = nums[j];
 }
```
  正确写法：
```
for(let j =i+1;j<length;j++){
    nums[j-1] = nums[j];
 }
```
  外面令j=i+1，这样里面就算是[j-1]也不会溢出。
  我的写法问题出在，没有全部遍历数组。（还是用动画理解）
思路2:双指针法

通过一个快指针和一个慢指针在一个for下完成两个for的循环工作

定义快慢指针：

快指针：找新数组需要的元素（比如数组[1,2,3]题目要求删除3，那快指针就会先后找到1，2这两个元素）
慢指针：需要更新的下标值（快指针获取到的元素赋值给慢指针下标值对应的位置就可以了）

不管是快慢指针都是在同一个数组上操作的,最后返回的就是slow指针的长度

3.2 拓展题目

26.删除有序数组的重复项

这个要求原地修改数组，就没法用额外空间开销的方法，我一开始看到题目的想法是，for遍历一遍，用库函数比较当前元素是不是在新建的数组里，没在就push进去，在就continue。可以实现，用array.indexof(i)与-1比较，相等就说明没有该元素，就可以array.push()

但是这样就不符合原地的说法了。所以用到双指针。

这个题的双指针有趣在他的快指针是从第二位开始的，因为题目目的是为了比较。

283.移动0

这题一开始我的思路是fast和slow都从后面遍历，fast发现是0的目标元素就和slow的值调换，再把slow的值换成0，往前移，但是这样就没法做到和原本的顺序一样了，
于是我分别写了两个for，第一个for就是正常从0开始的双指针，但是这一遍无视0，不是0的元素放到slow上，这个for结束后接另个for，用来把slow没碰到的元素变成0.

Day1 数组理论基础 || 704 二分查找 || 27 移除元素