一些算法基础知识点和leetcode题解，语言是python。来源于这里。

1 数组定义

数组：在连续的内存空间中，存储一组相同类型的元素。

  • 连续的内存空间：如果在内存空间上不连续，就是链表了。
  • 相同类型：[1,2,3]就是相同类型，而[1,‘a’,1.1]就不是。
  • 数组的索引是从0开始的，表示相对位置。
  • 数组访问（Access）：通过索引去访问某一个元素。
  • 数组搜索（Search）：查找某一个元素是否存在，如果存在，返回索引。

  • 访问操作的时间复杂度为什么短？因为不需要遍历：

  • 搜索：需要从头到尾遍历数组寻找。最坏的情况是一直找到最末尾的数才找到。
  • 插入：假设在上图中的2后面插入一个数，那么因为数组是连续的，需要把3向后移一位才行。最坏的情况是在索引为0的元素前面插入一个元素，那就要把所有元素全都后移。
    还有一种情况是插入元素后，数组所在的位置已经不够用了，那就需要重新找一个新的位置，把所有的元素全都移进去。
  • 删除：同理，删掉上图中的2后，3要往前移。最坏的情况是删除索引为0的元素，那所有的元素都要往前移。

总结：数组适用于“读”的操作，而不适用于“写”。读多写少。

2 Python数组常用操作

python中没有内置的数组，要用list模拟。

2.1 创建数组

a = []

2.2 添加元素
尾部添加元素：O(1)或O(N)->后者对应位置不够用，要找新位置的情况

a.append(1)
a.append(2)
a.append(3)
# [1,2,3]

中间插入元素： O(N)

a.insert(2, 99)
# [1,2,99,3]

2.3 访问元素

# O(1)
temp = a[2]
print(temp) # 99

2.4 更新元素

# O(1)
a[2] = 88
# [1,2,88,3]

2.5 删除元素
O(N)：

a.remove(88)  # 需要从头到尾遍历，找到88，然后删除
# [1,2,3]

a.pop(1)  # 删除索引1对应的元素，后面的元素要前移
# [1,3]

O(1)：

a.pop()  # 删除最后一个元素，然后不需要挪动元素
# [1]

2.6 获取数组长度

a = [1,2,3]
len(a)
# 3

2.7 遍历数组

# O(N)
# 方法一：
for i in a:
    print(i)

# 方法二：
for index, element in enumerate(a):  # enumerate()函数会返回索引和元素
    print("Index at ", index, "is: ", element)

# 方法三：
for i in range(0, len(a)):
    print("i: ", i, " element: ", a[i])

2.8 查找某个元素

# O(N)
index = a.index(2)  # 返回这个元素对应的索引
# 1

2.9 数组排序

# O(NlogN)
# 从小到大
a = [3,1,2]
a.sort()
# [1,2,3]

# 从大到小
a.sort(reverse=True)
# [3,2,1]

3 力扣题目训练
【数组】力扣283题：移动0
【数组】力扣27题：移除元素
【数组】力扣26题：删除有序数组中的重复项
【数组】力扣80题：删除有序数组中的重复项 II
【数组】力扣75题：颜色分类