面试问题：从未排序的链接列表中删除重复项
我正在阅读Cracking the Coding Interview，第四版：150编程面试问题和解决方案 ，我正在尝试解决以下问题：
2.1编写代码以从未排序的链表中删除重复项。 关注：如果不允许临时缓冲区，您将如何解决此问题？
我在C＃中解决它，所以我创建了自己的Node类：
public class Node where T : class { public Node Next { get; set; } public T Value { get; set; } public Node(T value) { Next = null; Value = value; } }
我的解决方案是遍历列表，然后为每个节点迭代通过列表的其余部分并删除任何重复项（请注意，我没有按照本书的指示实际编译或测试它）：
public void RemoveDuplicates(Node head) { // Iterate through the list Node iter = head; while(iter != null) { // Iterate to the remaining nodes in the list Node current = iter; while(current!= null && current.Next != null) { if(iter.Value == current.Next.Value) { current.Next = current.Next.Next; } current = current.Next; } iter = iter.Next; } }
这是本书的解决方案（作者用java编写）：
如果没有缓冲区，我们可以使用两个指针进行迭代：“current”执行正常迭代，而“runner”遍历所有先前节点以检查重复。 Runner每个节点只能看到一个dup，因为如果有多个重复项，它们就已经被删除了。
public static void deleteDups2(LinkedListNode head) { if (head == null) return; LinkedListNode previous = head; LinkedListNode current = previous.next; while (current != null) { LinkedListNode runner = head; while (runner != current) { // Check for earlier dups if (runner.data == current.data) { LinkedListNode tmp = current.next; // remove current previous.next = tmp; current = tmp; // update current to next node break; // all other dups have already been removed } runner = runner.next; } if (runner == current) { // current not updated - update now previous = current; current = current.next; } } }
所以我的解决方案总是寻找当前节点到最后的重复，而他们的解决方案寻找从头到当前节点的重复。 我觉得这两种解决方案都会遇到性能问题，具体取决于列表中有多少重复项以及它们如何分布（密度和位置）。 但总的来说：我的答案几乎与书中的答案一样好，还是更糟糕？
如果你给一个人一条鱼，他们会吃一天。 如果你教人钓鱼……
我对实施质量的衡量标准是：
- 正确性 ：如果在所有情况下都没有得到正确的答案，那么它还没有准备好
- 可读性/可维护性 ：查看代码重复，可理解的名称，每个块/方法的代码行数（以及每个块执行的操作数），以及跟踪代码流的难度。 如果您想了解更多相关信息，请查看任何数量的书籍，重点关注重构，编程最佳实践，编码标准等。
- 理论性能 （最坏情况和非常规）： Big-O是您可以使用的指标。 应该测量CPU和内存消耗
- 复杂性 ：估计一般的专业程序员如何实施（如果他们已经知道算法）。 看看这是否符合实际问题的难度
至于你的实施：
- 正确性 ：我建议编写unit testing来自己确定和/或从头到尾调试它（在纸上）有趣的样本/边缘情况。 空，一项，两项，各种重复项等
- 可读性/可维护性 ：它看起来很好，尽管你的最后两条评论没有添加任何内容。 你的代码所做的比书中的代码更明显
- 表现 ：我相信两者都是N平方。 无论摊销成本是否较低，我都会让你弄清楚:)
- 实施时间 ：普通专业人员应该能够在睡眠中对此算法进行编码，因此看起来很好
没有太大的区别。 如果我已经完成了我的数学计算，你的平均N / 16比作者慢，但是你的实现速度更快的情况很多。
编辑：
我将把你的实现Y和作者的A称为
两种提出的解决方案都具有O（N ^ 2）作为最坏情况，并且当所有元素是相同值时它们都具有O（N）的最佳情况。
编辑：这是一个完整的重写。 受到评论中的争议的启发，我试图找到随机N个随机数的平均情况。 这是具有随机大小和随机分布的序列。 平均情况是什么？
Y将始终运行U次，其中U是唯一数字的数量。 对于每次迭代，它将进行NX比较，其中X是迭代之前移除的元素数（+1）。 第一次没有元素被移除，并且在第二次迭代时平均将被删除N / U.
这是平均½N将被重复。 我们可以将平均成本表示为U *½N。 平均U可以基于N表示，也可以表示0
表达A变得更加困难。 假设我们在遇到所有唯一值之前使用迭代。 之后将在1和U之间进行比较（平均为U /“）并且将执行NI时间。
我* C + U / 2（NI）
但是我们在第一次迭代中运行的平均比较次数（c）是多少。 平均而言，我们需要与已经访问过的元素的一半进行比较，平均而言我们已经访问了I / 2元素，即。 C = I / 4
I / 4 + U / 2（NI）。
我可以用N来表示。平均而言，我们需要在N上访问一半以找到唯一值，因此I = N / 2得到平均值
（I ^ 2）/ 4 + U / 2（NI）可以减少到（3 * N ^ 2）/ 16。
当然，如果我对平均值的估计是正确的。 对于任何潜在序列来说，平均而言，A的比较比Y少了16个，但是在Y比A快的情况下存在很多情况。所以我认为它们与比较的数量相比是相等的。
如何使用HashMap？ 这样就需要O（n）时间和O（n）空间。 我会写psuedocode。
function removeDup(LinkedList list){ HashMap map = new HashMap(); for(i=0; i
当然我们假设HashMap有O（1）读写。
另一种解决方案是使用mergesort并从列表的开头到结尾删除重复项。 这需要O（n log n）
mergesort是O（n log n）从排序列表中删除重复是O（n）。 你知道为什么吗？ 因此整个操作需要O（n log n）
Heapsort是一种就地排序。 您可以修改“siftUp”或“siftDown”函数，以便在遇到相等的父级时简单地删除该元素。 这将是O（n log n）
function siftUp(a, start, end) is input: start represents the limit of how far up the heap to sift. end is the node to sift up. child := end while child > start parent := floor((child - 1) ÷ 2) if a[parent] < a[child] then (out of max-heap order) swap(a[parent], a[child]) child := parent (repeat to continue sifting up the parent now) else if a[parent] == a[child] then remove a[parent] else return
您的解决方案与作者一样好，只有它在实现中有错误:)尝试在具有相同数据的两个节点的列表上进行跟踪。
你的方法只是本书的镜面！ 你往前走，这本书倒退了。 没有区别，因为你们都扫描所有元素。 并且，是的，因为不允许缓冲区，所以存在性能问题。 您通常不必考虑使用此类经过培训的问题以及未明确要求的情况。
面试问题是为了测试你的开放思想。 我对Mark的答案有疑问：它肯定是实际例子中的最佳解决方案，但即使这些算法使用常量空间，也必须遵守不允许临时缓冲区的约束。
否则，我想这本书会采用这种方法。 马克，请原谅我批评你。
无论如何，只是为了更深入地解决这个问题，你和本书的方法都需要Theta(n^2)时间，而Mark的方法需要Theta(n logn) + Theta(n)时间，这导致Theta(n logn) 。 为什么Theta ？ 因为比较交换算法也是Omega(n logn) ，所以请记住！
java中的代码：
public static void dedup(Node head) { Node cur = null; HashSet encountered = new HashSet(); while (head != null) { encountered.add(head.data); cur = head; while (cur.next != null) { if (encountered.contains(cur.next.data)) { cur.next = cur.next.next; } else { break; } } head = cur.next; } }
在cpp尝试了同样的事情。 请告诉我你对此的评论。
// ConsoleApplication2.cpp：定义控制台应用程序的入口点。 //
#include "stdafx.h" #include struct node { int data; struct node *next; }; struct node *head = (node*)malloc(sizeof(node)); struct node *tail = (node*)malloc(sizeof(node)); struct node* createNode(int data) { struct node *newNode = (node*)malloc(sizeof(node)); newNode->data = data; newNode->next = NULL; head = newNode; return newNode; } bool insertAfter(node * list, int data) { //case 1 - insert after head struct node *newNode = (node*)malloc(sizeof(node)); if (!list) { newNode->data = data; newNode->next = head; head = newNode; return true; } struct node * curpos = (node *)malloc(sizeof(node)); curpos = head; //case 2- middle, tail of list while (curpos) { if (curpos == list) { newNode->data = data; if (curpos->next == NULL) { newNode->next = NULL; tail = newNode; } else { newNode->next = curpos->next; } curpos->next = newNode; return true; } curpos = curpos->next; } } void deleteNode(node *runner, node * curr){ //DELETE AT TAIL if (runner->next->next == NULL) { runner->next = NULL; } else//delete at middle { runner = runner->next->next; curr->next = runner; } } void removedups(node * list) { struct node * curr = (node*)malloc(sizeof(node)); struct node * runner = (node*)malloc(sizeof(node)); curr = head; runner = curr; while (curr != NULL){ runner = curr; while (runner->next != NULL){ if (curr->data == runner->next->data){ deleteNode(runner, curr); } if (runner->next!=NULL) runner = runner->next; } curr = curr->next; } } int _tmain(int argc, _TCHAR* argv[]) { struct node * list = (node*) malloc(sizeof(node)); list = createNode(1); insertAfter(list,2); insertAfter(list, 2); insertAfter(list, 3); removedups(list); return 0; }
C中的代码：
void removeduplicates(N **r) { N *temp1=*r; N *temp2=NULL; N *temp3=NULL; while(temp1->next!=NULL) { temp2=temp1; while(temp2!=NULL) { temp3=temp2; temp2=temp2->next; if(temp2==NULL) { break; } if((temp2->data)==(temp1->data)) { temp3->next=temp2->next; free(temp2); temp2=temp3; printf("\na dup deleted"); } } temp1=temp1->next; } }
这是C中的答案
void removeduplicates(N **r) { N *temp1=*r; N *temp2=NULL; N *temp3=NULL; while(temp1->next!=NULL) { temp2=temp1; while(temp2!=NULL) { temp3=temp2; temp2=temp2->next; if(temp2==NULL) { break; } if((temp2->data)==(temp1->data)) { temp3->next=temp2->next; free(temp2); temp2=temp3; printf("\na dup deleted"); } } temp1=temp1->next; } }
C＃用于删除第一组迭代后留下的重复项的代码：
public Node removeDuplicates(Node head) { if (head == null) return head; var current = head; while (current != null) { if (current.next != null && current.data == current.next.data) { current.next = current.next.next; } else { current = current.next; } } return head; }