【Python 数据结构 3.顺序表】

目录

一、顺序表基本概念

1.顺序表的概念

2.顺序表的元素插入

元素插入的步骤

3.顺序表的元素删除

元素删除的步骤

4.顺序表的元素查找

元素查找的步骤

5.顺序表的元素索引

元素索引的步骤

6.顺序表的元素修改

元素修改的步骤

二、Python中的顺序表

1.顺序表的定义

2.顺序表的插入

3.顺序表的删除

4.顺序表的查找

5.顺序表的索引

三、顺序表实战

2057. 值相等的最小索引

思路与算法

1464. 数组中两元素的最大乘积

方法一、暴力遍历 

思路与算法

方法二、贪心算法

思路与算法

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

思路与算法

27. 移除元素

方法一 双指针 for循环

思路与算法

方法二 双指针 while循环

思路与算法

---

人随春好，春与人宜

                                —— 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 ireturn -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 <= 500
• 1 <= 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 = 0for 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 = 0for i in range(n):if nums[i] > nums[maxIndex]:maxIndex = isecondIndex = -1for i in range(n):if i == maxIndex:continueif secondIndex == -1 or nums[i] > nums[secondIndex]:secondIndex = ireturn (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] <= 104
• nums 已按 非严格递增 排列

思路与算法

初始化：定义变量 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 = 1for 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 <= 100
• 0 <= nums[i] <= 50
• 0 <= 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 = 0for i in range(n):if nums[i] != val:nums[k] = nums[i]k += 1return 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 -= 1else:l += 1return 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 = 3l !< r
循环就此结束
return l = 3
'''