目录
人随春好，春与人宜
—— 25.3.1
一、顺序表基本概念
1.顺序表的概念
顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引(或者叫下标)相关联，索引从 0开始递增
下图中，下面那排数字 0 到 9 代表的就是索引，天蓝色柱子上的数字，代表的则是顺序表中的元素，元素可以是整数，可以是浮点数，可以是任意类型，包括结构体或者对象等等
2.顺序表的元素插入
顺序表的元素插入，就是指给定一个索引和一个元素，将这个元素插入到对应的索引位置上，这个位置以后的所有元素都要往后移动一个位置
元素插入的步骤
第1步：判断插入位置是否合法，如果不合法则抛出异常(比如：原本只有5个元素，给定的索引是100，那显然这个位置是不合法的)。
第2步：如果顺序表已满，则需要扩容顺序表，一般是把原有顺序表的容量进行倍增。
第3步：将插入位置之后的元素向后移动，为新元素腾出空间，
第4步：将新元素插入到指定位置。
第5步：更新顺序表的大小。
3.顺序表的元素删除
顺序表的元素删除，就是指给定一个索引，将这个索引上的元素删除，并且把这个索引位置以后的所有元素都往前移动一个位置。
元素删除的步骤
第1步：判断删除位置是否合法，如果不合法则抛出异常。
第2步：如果删除位置为最后一个元素，直接将顺序表的大小减1。
第3步：如果删除位置不是最后一个元素，将删除位置之后的元素向前移动，覆盖要删除的元
素
第4步：更新顺序表的大小。
4.顺序表的元素查找
顺序表的元素查找，是指在顺序表中查找指定元素是否存在，如果存在则返回该元素的索引，否否则返回 -1。由于需要遍历整个顺序表进行元素对比，所以查找的时间复杂度为(n)。
元素查找的步骤
第1步：遍历整个顺序表，对顺序表中的每个元素，和指定元素进行比较，如果相等则返回当前的索引；
第2步：如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1
5.顺序表的元素索引
顺序表的元素索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度 O(1)。
元素索引的步骤
第1步：直接通过索引访问即可获得对应的元素；
6.顺序表的元素修改
顺序表的元素修改是指将顺序表中指定位置的元素更新为新的值。
元素修改的步骤
第1步：直接通过索引访问即可获得对应的元素，修改成指定的值；
二、Python中的顺序表
Python中的顺序表用Python内置数据结构 —— 列表 实现
1.顺序表的定义
添加元素：用Python内置数据结构列表的 append() 方法实现
append()：用于向切片、列表或容器的末尾添加元素。在 Go 语言中，append 还可以触发切片的扩容。
| 参数名 | 类型 | 描述 |
|---|---|---|
| slice | []T |
要追加元素的切片或列表 |
| elems | ...T |
一个或多个要追加的元素 |
# 顺序表的定义
list = []
list.append(1)
list.append(2)
list.append(-5)
list.append(7)
list.append(9)
print(list)
2.顺序表的插入
插入元素：用Python内置数据结构列表的 insert() 方法实现
insert()：用于在列表或字符串的指定位置插入元素或子字符串。
| 参数名 | 类型 | 描述 |
|---|---|---|
| pos | int |
要插入的位置 |
| s2 | string |
要插入的字符串或元素 |
list.insert(2,3)
print(list)
3.顺序表的删除
删除元素：用Python内置数据结构列表的 remove() 和 pop() 方法实现
remove()：用于从列表中移除某个值的第一个匹配项。
| 参数名 | 类型 | 描述 |
|---|---|---|
| obj | T |
要移除的对象 |
pop()：用于从列表、字典或集合中移除并返回指定位置的元素。如果不指定索引，默认移除并返回最后一个元素。
| 参数名 | 类型 | 描述 |
|---|---|---|
| index | int |
要移除的元素的索引（可选） |
list.remove(-5)
print(list)
list.pop(1)
print(list)
4.顺序表的查找
查找元素：用Python内置数据结构列表的 index() 方法实现
index()：Python 中列表（list）对象的一个方法，用于查找某个元素在列表中首次出现的位置，并返回其索引值。如果元素不存在于列表中，该方法会抛出 ValueError 异常。
| 参数名 | 描述 | 默认值 | 示例 |
|---|---|---|---|
value |
要查找的元素或子字符串 | 无 | my_list.index(3) |
start |
查找的起始索引位置 | 0 |
my_list.index(3, 2) |
end |
查找的结束索引位置 | 列表或字符串的长度 | my_list.index(3, 2, 5) |
print(list.index(9))
5.顺序表的索引
下标（索引）从 0 开始
len()：用于返回字符串的字符数或变量的字节数。
| 参数名 | 类型 | 描述 |
|---|---|---|
| string | string |
要计算长度的字符串 |
| varname | variant |
要计算字节数的变量 |
print(list)
print(len(list))
print(list[2])
三、顺序表实战
2057. 值相等的最小索引
给你一个下标从 0 开始的整数数组
nums，返回nums中满足i mod 10 == nums[i]的最小下标i；如果不存在这样的下标，返回-1。
x mod y表示x除以y的 余数 。示例 1：
输入：nums = [0,1,2] 输出：0 解释： i=0: 0 mod 10 = 0 == nums[0]. i=1: 1 mod 10 = 1 == nums[1]. i=2: 2 mod 10 = 2 == nums[2]. 所有下标都满足 i mod 10 == nums[i] ，所以返回最小下标 0示例 2：
输入：nums = [4,3,2,1] 输出：2 解释： i=0: 0 mod 10 = 0 != nums[0]. i=1: 1 mod 10 = 1 != nums[1]. i=2: 2 mod 10 = 2 == nums[2]. i=3: 3 mod 10 = 3 != nums[3]. 2 唯一一个满足 i mod 10 == nums[i] 的下标示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9,0] 输出：-1 解释：不存在满足 i mod 10 == nums[i] 的下标示例 4：
输入：nums = [2,1,3,5,2] 输出：1 解释：1 是唯一一个满足 i mod 10 == nums[i] 的下标
思路与算法
函数定义：smallestEqual 函数接受一个整数列表 nums 作为输入，并返回一个整数。
遍历数组：使用 for 循环遍历数组 nums，i 是当前下标。
条件判断：在循环中，检查当前下标 i 是否满足 i % 10 == nums[i]。如果满足，则立即返回 i。
返回结果：如果遍历完整个数组都没有找到满足条件的下标，则返回 -1
class Solution:
def smallestEqual(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
if i % 10 == nums[i]:
return i
return -1
1464. 数组中两元素的最大乘积
给你一个整数数组
nums，请你选择数组的两个不同下标i和j，使(nums[i]-1)*(nums[j]-1)取得最大值。请你计算并返回该式的最大值。
示例 1：
输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。示例 2：
输入：nums = [1,5,4,5] 输出：16 解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。示例 3：
输入：nums = [3,7] 输出：12提示：
2 <= nums.length <= 5001 <= nums[i] <= 10^3
方法一、暴力遍历
思路与算法
双重循环：外层循环遍历数组中的每个元素，内层循环遍历当前元素之后的所有元素，确保每对元素只被计算一次。
乘积计算：对于每对元素 (nums[i], nums[j])，计算 (nums[i]-1) * (nums[j]-1)，并与当前的最大值 max 进行比较，更新 max。
返回值：最终返回 max，即数组中两元素的最大乘积。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
max = 0
for i in range(n):
for j in range(i + 1, n):
if (nums[i]-1) * (nums[j]-1) >= max:
max = (nums[i]-1) * (nums[j]-1)
return max
方法二、贪心算法
思路与算法
第一步：找到数组中最大元素的索引 maxIndex。
第二步：找到数组中第二大的元素的索引 secondIndex（排除 maxIndex）。
第三步：返回 (nums[maxIndex] - 1) * (nums[secondIndex] - 1)。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
maxIndex = 0
for i in range(n):
if nums[i] > nums[maxIndex]:
maxIndex = i
secondIndex = -1
for i in range(n):
if i == maxIndex:
continue
if secondIndex == -1 or nums[i] > nums[secondIndex]:
secondIndex = i
return (nums[maxIndex] - 1) * (nums[secondIndex] - 1)
26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组
nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。考虑
nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。- 返回
k。判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按 非严格递增 排列
思路与算法
初始化：定义变量 n 为数组的长度，k 为去重后数组的索引，初始值为 1。k 表示当前不重复元素的最后一个位置。
遍历数组：从数组的第二个元素开始遍历（i 从 1 到 n-1），比较当前元素 nums[i] 与前一个元素 nums[i - 1]。如果 nums[i] 不等于 nums[i - 1]，说明 nums[i] 是一个新的不重复元素，将其赋值给 nums[k]，并将 k 增加 1。如果 nums[i] 等于 nums[i - 1]，则跳过该元素，继续遍历。
返回结果：遍历结束后，k 即为去重后数组的长度。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
k = 1
for i in range(1, n):
# 第二个元素nums[1] 如果不等于 第一个元素nums[0]，则把第二个元素nums[1]赋值给第一个元素所在位置nums[0]
if nums[i] != nums[i - 1]:
nums[k] = nums[i]
k += 1
return k
27. 移除元素
给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设
nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。- 返回
k。用户评测：
评测机将使用以下代码测试您的解决方案：
int[] nums = [...]; // 输入数组 int val = ...; // 要移除的值 int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。 int k = removeElement(nums, val); // 调用你的实现 assert k == expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素 for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; }如果所有的断言都通过，你的解决方案将会 通过。
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_] 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_] 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
方法一 双指针 for循环
思路与算法
双指针法：使用两个指针 i 和 k，其中 i 用于遍历数组，k 用于记录新数组的长度。
遍历数组：从头到尾遍历数组 nums，当遇到不等于 val 的元素时，将其放到 nums[k] 的位置，并将 k 加 1。
返回新长度：遍历结束后，k 即为新数组的长度。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
k = 0
for i in range(n):
if nums[i] != val:
nums[k] = nums[i]
k += 1
return k
'''
第一轮
[1 1 1 2 5 7] 1
k = 0
i = 0
nums[i] = 1
nums[i] == val
k = 0
第二轮
[1 1 1 2 5 7] 1
k = 0
i = 1
nums[i] = 1
nums[i] == val
k = 0
第三轮
[1 1 1 2 5 7] 1
k = 0
i = 2
nums[i] = 1
nums[i] == val
k = 0
第四轮
[1 1 1 2 5 7] 1
k = 0
i = 3
nums[i] = 2
nums[i] != val
k = 1
第五轮
[1 1 1 2 5 7] 1
k = 1
i = 4
nums[i] = 5
nums[i] != val
k = 2
第六轮
[1 1 1 2 5 7] 1
k = 2
i = 5
nums[i] = 7
nums[i] != val
k = 3
'''
方法二 双指针 while循环
思路与算法
初始化指针：r指向数组的末尾，l指向数组的开头。
遍历数组：当l < r时，检查nums[l]是否等于val。如果等于val，则将nums[r-1]的值赋给nums[l]，并将r指针左移一位。如果不等于val，则将l指针右移一位。
返回结果：最终返回l，即移除指定元素后的新长度。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
r = len(nums)
l = 0
while l < r:
if nums[l] == val:
nums[l] = nums[r-1]
r -= 1
else:
l += 1
return l
'''
第一轮
[1 1 1 2 5 7] 1
l = 0, r = 6
nums[l] = 1
nums[l] == val
nums = [7 1 1 2 5 7]
r = 5
l = 0
第二轮
[7 1 1 2 5 7] 1
l = 0, r = 5
nums[l] = 7
nums[l] != val
r = 5
l = 1
第三轮
[7 1 1 2 5 7] 1
l = 1, r = 5
nums[l] = 1
nums[l] == val
nums = [7 5 1 2 5 7]
r = 4
l = 2
第四轮
[7 5 1 2 5 7] 1
l = 2, r = 4
nums[l] = 1
nums[l] == val
nums = [7 5 7 2 5 7]
r = 3
l = 2
第五轮
[7 5 7 2 5 7] 1
l = 2, r = 3
nums[l] = 7
nums[l] != val
nums = [7 5 7 2 5 7]
r = 3
l = 3
l !< r
循环就此结束
return l = 3
'''