Python编程题13--判断两个升序列表,其中一个是另外一个的
2020-10-08 本文已影响0人
wintests
题目
已知两个升序列表A、B,列表A的元素个数要小于列表B,请判断列表A是否是列表B的子集,如果是则返回 True ,否则返回 False 。
如果列表A是列表B的子集,需要满足以下两个条件:
- 列表A的所有元素都能在列表B中找到;
- 列表A中重复元素的个数不能大于列表B中重复元素的个数。
实现思路1
这里我们运用 Python
里面 集合 的 issubset()
方法来处理问题。
- 分别把列表A和列表B转换为新的两个集合,通过
set(列表名)
来完成 - 通过集合的
issubset()
方法,判断集合的所有元素是否都包含在指定集合中,如果是则返回 True,否则返回 False
注意:因为集合是不包含重复元素的,如果列表A或列表B包含重复元素,那么转换为集合时会进行去重,也就不能直接使用 issubset()
方法来实现。
代码实现
def is_sub_set(short_list, long_list):
set1, set2 = set(short_list), set(long_list)
return set1.issubset(set2)
# 列表A和列表B不包含重复元素
A = [1, 2, 4, 5]
B = [1, 2, 3, 4, 5, 6, 7]
print(is_sub_set(A, B))
实现思路2
- 求出列表A和列表B的长度 len1、len2,并设置两个变量 x、y ,分别用于标记列表A和列表B的索引下标
- 使用
while
循环语句,只要同时满足 x索引下标小于 len1、y索引下标小于 len2 ,那么就一直就行循环,否则说明列表A或列表B已经遍历结束 - 循环过程中,如果列表A下标为 x 的元素,恰等于列表B下标为 y 的元素,那么说明A、B均存在该元素,所以让 x、y 索引下标均加1,继续往下进行比较
- 如果列表A下标为 x 的元素,大于列表B下标为 y 的元素,那么让 y 加1,x 保持不变,继续往下进行比较
- 如果列表A下标为 x 的元素,小于列表B下标为 y 的元素,而A、B均为升序列表,那么就说明列表A的这个元素,一定不存在于列表B中,所以直接返回 False
- 循环结束后,只需比较列表A的索引下标 x ,是否等于其长度 len1 ,如果等于则说明 列表A 是列表B的子集
代码实现
def is_sub_set(short_list, long_list):
len1, len2 = len(short_list), len(long_list)
x, y = 0, 0
while x < len1 and y < len2:
if short_list[x] == long_list[y]:
x += 1
y += 1
elif short_list[x] > long_list[y]:
y += 1
else:
return False
return True if x == len1 else False
A = [1, 2, 3, 3, 4, 5]
B = [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
print(is_sub_set(A, B))
实现思路3
- 求出列表A和列表B的长度 len1、len2,并设置两个变量 m、flag,m 用于标记列表A中有 m 个元素存在于列表B中,flag 用于标记列表A是否为B的子集
- 遍历列表B,每次将列表B的元素,与列表A的第一个元素进行比较,如果相等,那么让 m 加1,并把列表A的第一个元素从列表中删除
- 如果 m 等于 len1, 那么表示列表A的元素均存在与列表B中,且其重复元素个数肯定小于列表B中重复元素的个数,所以将 flag 置为 True,并通过
break
结束循环
代码实现
def is_sub_set(short_list, long_list):
len1, len2 = len(short_list), len(long_list)
m = 0
flag = False
for i in range(len2):
if long_list[i] == short_list[0]:
m += 1
if m == len1:
flag = True
break
del short_list[0]
return flag
A = [1, 2, 3, 3, 4, 5]
B = [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
print(is_sub_set(A, B))
更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)