《算法设计与分析基础》（Python语言描述） 课件 第2章常用的数据结构及其应用(1).pptx

第2章工之利器—常用的数据结构及其应用;2/83;2.1线性表—数组;2.1.2Python列表;1）访问列表中的值

2）列表脚本操作符

3）列表的函数

4）列表的方法;;;;2.1.3列表元素排序;对于多关键字排序，key可以使用operator模块提供的itemgetter函数获取对象的哪些维的数据实现排序。;可以制定自定义的比较规则;2.1.4列表的拷贝;1 importcopy #导入copy模块

2 a=[1,[1,2,3],4]

3 b=copy.deepcopy(a)

4 print(a) #输出：[1,[1,2,3],4]

5 print(b) #输出：[1,[1,2,3],4]

6 b[0]=3

7 b[1][0]=3

8 print(a) #输出：[1,[1,2,3],4]

9 print(b) #输出：[3,[3,2,3],4];1 a=[1,[1,2,3],4]

2 b=a.copy()

3 print(a) #输出：[1,[1,2,3],4]

4 print(b) #输出：[1,[1,2,3],4]

5 b[0]=3

6 b[1][0]=3

7 print(a) #输出：[1,[3,2,3],4]

8 print(b) #输出：[3,[3,2,3],4];2.1.5实战—移除元素（LeetCode27★）;解法1：整体建表法。用nums存放删除所有val元素的结果，先将结果数组nums看成是一个空表，用k表示结果数组的元素个数（初始为0），用i遍历nums，遇到保留元素（不等于val）时重新插入到结果数组nums中，遇到val元素时跳过。最后返回k。;1 class?Solution:

2 def?removeElement(self,nums:List[int],val:int)-int:

3????? n=len(nums)

4???????k,i=0,0??????????? #k记录结果数组中的元素个数

5?????? while?in:

6????????? if?nums[i]!=val:??? #nums[i]是保留的元素

7?????????? nums[k]=nums[i];?? #将nums[i]重新插入到结果数组中

8??????????? k+=1?? #结果数组的长度增1

9???????? i+=1

10????? return?k?????????? #返回保留的元素个数;解法2：移动法。同样用nums存放删除所有val元素的结果，先将结果数组看成是整个表，用k表示要删除的元素个数（初始为0），用i遍历nums：

①遇到保留元素（不等于val）时将nums[i]前移k个位置。

②遇到val元素时将k增1。

遍历完毕返回结果数组的长度n-k。;1 class?Solution:

2???? def?removeElement(self,nums:List[int],val:int)-int:

3???? n=len(nums)

4?????? k,i=0,0? #k记录结果数组中的元素个数

5?????? while?in:

6??????? if?nums[i]!=val:?? #nums[i]是保留的元素

7?????????? nums[i-k]=nums[i]? #将nums[i]前移k个位置

8???????? else:?? #nums[i]是要删除的元素

9???? k+=1??????? #k增1

10?????? i+=1

11???? return?n-k???????? #返回结果数组的长度n-k;解法3：区间划分法。用v[0..k]（共k+1个元素）表示保留的元素区间（即不为val区间），初始时保留区间为空，所以置k=-1。

v[k+1..i-1]（共i-k-1个元素）表示删除元素区间（即为val的区间），i从0开始遍历v，初始时删除区间也为空。;;1 class?Solution:

2???? def?removeElement(self,nums:List[int],val:int)-int:

3????? n=len(nums)

4???????k,i=-1,0???? #k记录结果数组中的元素个数

5?????? while?in:

6????????? if?nums[i]!=val:?? #nums[i]是保留的元素

7????????? k+=1????????