leetcode_day02
任务二:删除排序数组中的重复项
原文链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
最开始的解决思路:
遍历2次数组;
第一次,遍历整个数组,放置标记index1
第二次,从每一个第一次遍历的元素index1后面开始遍历index2.
然后,一个一个比较,重复的元素,删除后来再次重复的元素index2。
for index1 in range(0, len( num_list) - 1):
for index2 in range(index1, len( num_list)):
if num_list[index1] == num_list[index2]:
del num_list[index2]
1.遇到的问题:每次del删除数组元素之后,数组本身以及数组长度发生变化,但是,for循环中的range()函数不会再次求值len(num_list)。
导致,Num_list数组去重之后,缩短了,但是len(num_list)还是原来的长度。
最终导致,数组越界异常。
核心:数组可变,删除元素,导致数组长度变化。与遍历数组,冲突。
解决方法:遍历比较功能,和删除元素功能分开。比较得到的重复元素,先进行标记,然后统一再删除。
class Solution:
def removeDuplicates(self, origin_list):
length = len(origin_list)
print(origin_list)
#遍历比较
#先取出第一个元素
for index1 in range(0, length - 1):
#再取出第二个元素
for index2 in range(index1 + 1, length):
#比较index1元素和index2元素2,如果index2重复则删除
if origin_list[index1] == origin_list[index2]:
#不能删除,则对要删除元素做标记
origin_list[index2] = 'null'
print(origin_list)
#删除所有null值元素
for ele in origin_list:
if ele == 'null':
origin_list.remove('null') new_length = len(origin_list)
return origin_list
2.遇到的问题:
1 for ele in origin_list:
2 if ele == 'null':
3 origin_list.remove('null')
这段代码,无法将origin_list列表中的重复值全部去除,
原因:列表在remove时,本身发生了变化。列表的刚刚索引,也发生了变化。
解决方法:使用while循环:
while 'null' in num_list:
num_list.remove("null")
3.遇到的问题:
时间过长。
解决方法:仔细看题发现,原来,本题是已经排好顺序的数组。所以index2没必要把index1后面全部遍历,只需要遍历到第一个和index1的值不同位置即可,后面就全都是不同值。
class Solution:
def removeDuplicates(self, origin_list):
length = len(origin_list)
#print(origin_list)
for index1 in range(0, length - 1):
for index2 in range(index1 + 1, length):
#将重复值,标记成null,后面再统一删除
if origin_list[index1] == origin_list[index2]:
origin_list[index2] = 'null'
else:
break
#print(origin_list)
#将数组中的Null值全部删除
while 'null' in origin_list:
origin_list.remove('null')
new_length = len(origin_list)
return origin_list
总结:
1.for循环:
x = 4
for i in range(0, x):
print(i)
x = 5
在for循环内部,改变X的值,不能改变迭代次数。
因为,在执行for循环这行代码中,range()函数的参数X,在循环的第一次循环之前,就已经被python解释器求值(X=4),随后不会的循环中不会再次求值。
例如:
x = 4
for j in range(x):
for i in range(x):
print(i)
x = 2
答案:
0
1
2
3
0
1
0
1
0
1
2.remove()函数,list.remove()会改变列表本身
3.列表去重:
3.1set():
ser(num_list)
3.2while去重:
while 重复值 in num_list:
num_list.remove(重复值)
3.3把列表复制一份,用新列表里面,重复元素的索引index值,删除原列表的值
3.4 倒序去重:
for i in range(length -1, -1, -1):
if origin_list[i] == 'null':
del origin_list[i]
最新文章
- The Google Test and Development Environment (持续更新)
- 【板子】gcd、exgcd、乘法逆元、快速幂、快速乘、筛素数、快速求逆元、组合数
- CodeForces 710F 强制在线AC自动机
- Android FM模块学习之四源码分析(3)
- Java编程思想学习(六) 多态
- 利用selenium Server实现IE firefox 和 chrome兼容性测试
- virtualenvwrapper
- 在Debian中安装VMware Workstatption 12
- HDU-4720 Naive and Silly Muggles 圆的外心
- poj2079
- java保留两位小数的方法
- struts2中修改Action后刷新浏览器后不能及时更新
- CA
- hdu 5640 King's Cake(模拟)
- ";windows 正在启动";
- Matalab之模糊KMeans实现
- LOJ6000 - 「网络流 24 题」搭配飞行员
- spring+mybatis+c3p0数据库连接池或druid连接池使用配置整理
- [BZOJ1212][HNOI2004]L语言
- post方式接口测试(一)_新建测试用例