899
CareerCup之2.1無序鏈表刪除重複元素
【題目】
原文：
2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
譯文：
從一個未排序的鏈表中移除重複的項
進一步地，
如果不允許使用臨時的緩存，你如何解決這個問題？
【分析】
（1）如果可以使用額外的存儲空間，我們就開一個數組來保存一個元素的出現情況。 對於這種情況，最好的解決方法當然是使用哈希表，但令人非常不爽的是C++標準裏是沒有 哈希表的(java裏有)。所以，在這用一個數組模擬一下就好了。但，這裏要注意一個問題， 就是元素的邊界，比如鏈表裏存儲的是int型變量。那麼，如果有負值，這個方法就不奏效 了。而如果元素裏的最大值非常大，那麼這個數組也要開得很大，而數組中大部分空間是用 不上的，會造成空間的大量浪費。
簡言之，如果可以用哈希表，還是用哈希表靠譜。
如下代碼遍曆一遍鏈表即可，如果某個元素在數組裏記錄的是已經出現過， 那麼將該元素刪除。時間複雜度O(n):
（2）如果不允許使用臨時的緩存(即不能使用額外的存儲空間)，那需要兩個指針，cur做正常的迭代，runner指針遍曆cur指針之前的所有元素，判斷當前元素的值是否已經出現過。如果出現過就刪除cur指向的元素。
【代碼一】
/*********************************
* 日期：2014-05-17
* 作者：SJF0115
* 題目: Set Matrix Zeroes
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100000
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool Hash[N];
ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
memset(Hash,0,sizeof(Hash));
ListNode* pre = head;
ListNode* cur = head->next;
while(cur != NULL){
//存在重複元素刪除
if(Hash[cur->val]){
ListNode* node = cur;
pre->next = cur->next;
cur = cur->next;
delete node;
}
else{
Hash[cur->val] = true;
pre = cur;
cur = cur->next;
}
}
return head;
}
int main(){
int i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};
for(int i = 0;i < 18;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = DeleteDuplicatesFromUnSortedList(head);
ListNode* cur = head->next;
while(cur != NULL){
printf("%d ",cur->val);
cur = cur->next;
}
return 0;
}
【代碼二】
/*********************************
* 日期：2014-05-17
* 作者：SJF0115
* 題目: Set Matrix Zeroes
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
ListNode* pre = head;
ListNode* cur = head->next;
//刪除重複元素
while(cur != NULL){
ListNode* runner = head->next;
//判斷是否是重複
while(runner != cur){
if(runner->val == cur->val){
ListNode* node = cur;
//刪除node
pre->next = cur->next;
cur = pre->next;
delete node;
break;
}
runner = runner->next;
}
//如果上麵沒有刪除元素,需要更新指針
if(runner == cur){
pre = cur;
cur = cur->next;
}
}
return head;
}
int main(){
int i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};
//輸入
for(int i = 0;i < 18;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
//刪除重複元素
head = DeleteDuplicatesFromUnSortedList(head);
//輸出
ListNode* cur = head->next;
while(cur != NULL){
printf("%d ",cur->val);
cur = cur->next;
}
return 0;
}
最後更新：2017-04-03 08:26:11