已知 A,B 和 C 为三个递增有序的线性表,现要求对 A 表作如下操作:删去那些既在 B 表中出现又在 C 表中出现的元素。试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意:题中没 有特别指明同一表中的元素值各不相同
时间: 2023-03-19 13:22:38 浏览: 204
算法思路:
为了实现对 A 表的操作,我们可以采用双指针的方法。我们用两个指针 i 和 j 分别指向 A 表和 B 表,然后在 B 表中寻找 A 表中的元素,如果找到了,则在 C 表中寻找该元素,如果也找到了,则将该元素从 A 表中删除。最后返回修改后的 A 表。
算法实现:
```
def remove_common_elements(A, B, C):
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] == B[j]:
if A[i] in C:
A.pop(i)
else:
i += 1
j += 1
elif A[i] < B[j]:
i += 1
else:
j += 1
return A
```
算法分析:
该算法的时间复杂度为 O(n),其中 n 为 A 表的长度。因为算法的主要操作是在 A 表中查找元素,而 A 表是有序的,因此可以使用双指针的方法,将时间复杂度降低到线性级别。在查找元素的过程中,我们最多需要遍历 A 表一次,因此算法的时间复杂度为 O(n)。
相关问题
请用C语言写出 已知a,b和c为三个顺序线性表,现要求对a表作如下操作:删去 那些既在b表中出现又在c元素 的代码
#include <stdio.h>
void deleteSame(int a[], int b[], int c[], int lenA, int lenB, int lenC) {
int i, j, k;
for(i = 0; i < lenA; i++) {
for(j = 0; j < lenB; j++) {
if(a[i] == b[j]) {
for(k = 0; k < lenC; k++) {
if(a[i] == c[k]) {
int m;
for(m = i; m < lenA - 1; m++) {
a[m] = a[m+1];
}
lenA--;
i--;
break;
}
}
break;
}
}
}
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6};
int b[] = {2, 4, 6, 8, 10};
int c[] = {1, 3, 5, 7, 9};
int lenA = 6, lenB = 5, lenC = 5;
deleteSame(a, b, c, lenA, lenB, lenC);
int i;
for(i = 0; i < lenA; i++) {
printf("%d ", a[i]);
}
return 0;
}
已知A、B和C为3个递增有序的线性表,现要求对A表做如下操作,删除那些既在B中出现,也在C中出现的元素。以带表头结点的单链表作为线性表的物理结构,编写实现上述操作的算法。 函数原型:void TriLinkList(LinkList A,LinkList B,LinkList C);
算法思路:
1. 初始化三个指针分别指向A、B、C的头结点;
2. 依次比较指针所指向的结点的值,如果A的当前结点的值小于B和C的当前结点的值,则将A的指针向后移动一位;
3. 如果A的当前结点的值等于B和C的当前结点的值,则删除A的当前结点,并将A的指针指向下一个结点;
4. 如果A的当前结点的值大于B和C的当前结点的值,则将B和C的指针分别向后移动一位;
5. 重复2-4步,直到A、B、C中有任何一个链表的结点为空为止。
代码实现:
void TriLinkList(LinkList A, LinkList B, LinkList C)
{
LNode *pa = A->next, *pb = B->next, *pc = C->next; // 初始化三个指针
LNode *pre = A; // 指向A链表当前结点的前一个结点,方便删除操作
while (pa && pb && pc) // 只要三个链表中有任何一个为空,就停止循环
{
if (pa->data < pb->data || pa->data < pc->data) // A链表当前结点的值小于B和C链表当前结点的值
{
pre = pa; // 记录A链表当前结点的前一个结点
pa = pa->next; // A链表的指针向后移动一位
}
else if (pa->data == pb->data && pa->data == pc->data) // A链表当前结点的值等于B和C链表当前结点的值
{
pre->next = pa->next; // 删除A链表的当前结点
free(pa); // 释放删除的结点的内存空间
pa = pre->next; // A链表的指针指向下一个结点
}
else // A链表当前结点的值大于B和C链表当前结点的值
{
if (pb->data < pc->data) // B链表当前结点的值小于C链表当前结点的值
pb = pb->next; // B链表的指针向后移动一位
else // C链表当前结点的值小于B链表当前结点的值
pc = pc->next; // C链表的指针向后移动一位
}
}
}