已知两个顺序表a和b分别表示两个集合,其元素递增排列,编写一个函数求出a和b的交集c,要求c同样以元素递增的顺序表形式存储。
时间: 2023-04-18 20:00:13 浏览: 112
编写函数,建立一个顺序表并输出,计算该顺序表的长度。 实现在顺序表中查找第i个元素的值。实现在顺序表中第i个位置上插入值为x的
5星 · 资源好评率100%
可以使用双指针法来求解a和b的交集c。具体步骤如下:
1. 初始化两个指针i和j,分别指向a和b的第一个元素。
2. 循环比较a[i]和b[j]的大小,如果a[i]小于b[j],则i指针向后移动一位;如果a[i]大于b[j],则j指针向后移动一位;如果a[i]等于b[j],则将a[i]加入到交集c中,并将i和j指针同时向后移动一位。
3. 当其中一个指针到达序列末尾时,退出循环。
4. 返回交集c。
代码实现如下:
```python
def intersection(a, b):
i, j = ,
c = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
c.append(a[i])
i += 1
j += 1
return c
```
阅读全文