已知两个链表 A 和 B 分别表示两个集合,其元素递增排列。请设计算法求出两个集\n合 A 和 B 的差集(即仅由在 A 中出现而不在 B 中出现的元素所构成的集合) ,并以同样的形\n式存储,同时返回该集合的元素个数。代码
时间: 2023-04-04 19:04:45 浏览: 128
以下是算法的实现:
```
int getDifference(int *A, int lenA, int *B, int lenB, int *C) {
int i = 0, j = 0, k = 0;
while (i < lenA && j < lenB) {
if (A[i] < B[j]) {
C[k++] = A[i++];
} else if (A[i] > B[j]) {
j++;
} else {
i++;
j++;
}
}
while (i < lenA) {
C[k++] = A[i++];
}
return k;
}
```
其中,A 和 B 分别表示两个集合,C 表示它们的差集,lenA 和 lenB 分别表示 A 和 B 的长度。算法的思路是,使用两个指针 i 和 j 分别指向 A 和 B 的开头,然后比较它们的元素大小,如果 A[i] < B[j],则将 A[i] 加入到 C 中,然后 i++;如果 A[i] > B[j],则将 j++,表示 B 中没有 A[i] 这个元素;如果 A[i] == B[j],则表示 A 和 B 中都有这个元素,所以 i++ 和 j++。最后,如果 A 中还有剩余的元素,就将它们全部加入到 C 中。最后返回 C 的长度,即为差集的元素个数。
相关问题
已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集C
1. 初始化三个指针,分别指向链表A、B和C的头结点。
2. 遍历链表A和B,比较当前节点的值,如果A的值小于B的值,则将A的节点加入到C中,A指针后移;如果B的值小于A的值,则将B的节点丢弃,B指针后移;如果A和B的值相等,则丢弃两个节点,A和B指针同时后移。
3. 如果遍历完链表A后B还有剩余节点,将剩余节点加入到C中。
4. 返回链表C的头结点。
代码实现:
```
ListNode* getDifference(ListNode* A, ListNode* B) {
ListNode* C = new ListNode(0);
ListNode* pA = A;
ListNode* pB = B;
ListNode* pC = C;
while (pA != NULL && pB != NULL) {
if (pA->val < pB->val) {
pC->next = new ListNode(pA->val);
pA = pA->next;
pC = pC->next;
} else if (pA->val > pB->val) {
pB = pB->next;
} else {
pA = pA->next;
pB = pB->next;
}
}
while (pB != NULL) {
pB = pB->next;
}
return C->next;
}
```
已知两个链表a和b分别表示两个集合,其元素递增排列。请设计算法求出a与b的交集,并存放于a链表中
算法步骤如下:
1. 定义两个指针p1和p2,分别指向链表a和b的头结点。
2. 遍历链表a和b,比较p1和p2所指向的元素大小。
3. 如果p1所指向的元素小于p2所指向的元素,则p1指向下一个元素。
4. 如果p1所指向的元素大于p2所指向的元素,则p2指向下一个元素。
5. 如果p1和p2所指向的元素相等,则将该元素插入到新的链表c中,并同时将p1和p2指向下一个元素。
6. 遍历完a和b后,将链表c中的元素复制到链表a中。
代码实现如下:
```python
def intersection(a, b):
p1, p2 = a.head, b.head
c = LinkedList()
while p1 and p2:
if p1.data < p2.data:
p1 = p1.next
elif p1.data > p2.data:
p2 = p2.next
else:
c.append(p1.data)
p1 = p1.next
p2 = p2.next
a.clear()
for item in c:
a.append(item)
```
其中,LinkedList为链表类,head为头结点,append方法为在链表尾部添加元素,clear方法为清空链表。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)