今日学习的文章链接: 代码随想录

数组基础知识回顾

数组是连续空间内相同类型数据的集合

●  存储空间是连续的

●  下标都是从0开始

因为存储空间总是连续的，所以在增加和删除某个元素的时候就需要移动其他元素的地址

区别数组的访问与查找

数组的访问是根据索引看对应的元素，空间复杂度是O（1），比如在上图中访问s(3),因为知道数组第一个元素存在100，知道索引是3，可以根据数学方法算出来，100+3= 103，直接去103位置去访问，得到结果J。

数组的搜索/查找与访问不同，搜索是根据元素数值查找索引，要一个一个找，所以时间复杂度是O（n）

数组的操作查漏补缺

插入元素：a.insert(2,99) 在索引为2的位置插入数字99

两种删除：1⃣️根据数值删除：a.remove(88) 删除数值是88的元素，O(n)

                   2⃣️根据索引删除：a.pop(2) 删除索引在2的数值，O(n)

查找元素：index = a.index(2) 查找数值2的索引O(n)

遍历数组：for index, element in enumerate(a) 获取索引和其对应的值

倒序排序：a.sort(reverse = true)

704. 二分查找

题目链接：力扣

思路

因为是无重复值的有序数组，所以用二分查找，有两个难点：

1⃣️while(left < right)还是 while(left <= right)

2⃣️right = middle还是right = middle - 1

以上两个问题需要由边界得到，即用了左闭右闭区间还是左闭右开区间（闭是包括，开是不包括）

[1，1]是左闭右闭，包括了两个1，所以left和right可以相等

[1，1）是左闭右开，只包括一个1，left和right没法相等

1⃣️ 左闭右闭写法

​​​​​​​

2⃣️ 左闭右开写法

个人心得

刚开始不理解为什么会有左闭右闭和左闭右开这两种区间，后来想到是循环种类的原因，for i in range的循环左闭右开的，while循环如果右指针从n开始就相当于包含了最右边的，所以是左闭右闭。

27. 移除元素

题目链接：力扣

思路

数组的内存地址是连续的，它不是删除了二十用后面的元素覆盖了。

比如数组是[1,3,3,4,5]，删除3，要找3的时候要用i遍历这个数组，for i in range(len(nums) - 1)，i = 1时找到并删除第一个3，数组变成[1,3,4,5]，那是之后i = 2,相当于第二个3没有被遍历到。

既然不能直接删，就有两个思路

1⃣️暴力法

循环套循环，外层循环找到要删的数字，内层循环把后面的往前挪一位再进入下一次外层循环。

 

2⃣️双指针

快指针用来指不是目标的数字，只要不是目标值，就把值赋给慢指针。

注意，因为循环之后left += 1，所以左指针最后右往后走了一步，所以left是长度而不是left + 1

35. 搜索插入位置

题目链接：力扣