出题：给定一个乱序链表，节点值为ASCII字符，但是其中有重复项，要求去除重复项并保证不改变剩余项的原有顺序；
分析：创建一个256（2^8）大小的bool数组，初始化为false，顺序读取链表，将字母对应位置为false的重新标记为true并保留节点，将字母对 应位置为true的保持并删除节点；时间复杂度为O(N)，空间复杂度为常量。注意删除节点和不删除节点的情况下，pre和cur的移动操作不相同；
解题：
struct Node {
char value;
Node* next;
};
void DeleteDup(Node *head) {
if(head==NULL) {
printf("\nthe list is NULL");
return;
}
Node *pre=NULL, *cur=head;
/**
* 设置一个256的bool数组记录char是否
* 已经出现
* */
bool haveChar[];
for(int i=;i<;i++)
haveChar[i]=false;
/**
* 如果haveChar对应为true，说明当前节点
* 的值已经出现过，则进行删除
* 如果haveChar对应为false，说明当前节点
* 的值第一次出现，则将其设置为true
* */
while(cur!=NULL) {
/**
* 注意删除节点的情况和不删除节点的情况
* pre和cur的需要不同的处理
* */
if(!haveChar[(cur->value)-'']) {
haveChar[(cur->value)-'']=true;
pre=cur;
cur=cur->next;
}
else {
pre->next=cur->next;
delete cur;
cur=pre->next;
}
}
}
int main() {
Node *a1=new Node();a1->value='a';
Node *a2=new Node();a2->value='d';
Node *a3=new Node();a3->value='s';
Node *a4=new Node();a4->value='d';
a1->next=a2;a2->next=a3;
a3->next=a4;a4->next=NULL;
DeleteDup(a1);
Node *temp=a1;
while(temp!=NULL) {
printf("\n%c",temp->value);
temp=temp->next;
}
return ;
}
出题：给定两个已排序的数组，要求找出共同的元素；
分析：
- 如果两个数组大小接近，则分别使用指针first和second遍历两个序列，由于数组已经排序，所以遍历过的元素不会再次访问，所以时间复杂度为O(M+N)；
- 如果两个数组大小差距较大，则在针对小数组中的每个元素在大数组中使用二分查找（每处理一个元素之后，大数组的范围都可以调整到上一个元素的后面），时间复杂度为O(NlogM)，N足够小（M>N^2）；
解题：
/**
* 时间复杂度O(M+N)
* */
void FindCommonInt1(int *first, int fl, int *second, int sl) {
int ft=, st=;
while (ft<fl && st<sl) {
if(first[ft]>second[st]) {
st++;
} else if(first[ft]<second[st]) {
ft++;
} else {
printf("\n%d",first[ft]);
ft++;st++;
}
}
}
/**
* 时间复杂度小于O(NlogM)，其中M不断变小
* */
void FindCommonInt2(int *first, int fl, int *second, int sl) {
int start=, end=fl-;
int s,e,m;
for(int i=;i<sl;i++) {
s=start;e=end;
while(s<=e) {
m=(s+e)/;
if(first[m]>second[i]) {
e=m-;
} else if(first[m]<second[i]) {
s=m+;
} else {
printf("\n%d",first[m]);
start=m+;
break;
}
}
}
}
int main() {
int first[]={,,,,,,,,};
int second[]={,,,};
FindCommonInt2(first, , second, );
return ;
}