算法：从数组中删除重复整数的有效方法

Question

算法：从数组中删除重复整数的有效方法

我在接受微软的采访时遇到了这个问题。

给定一个随机整数数组，用C编写一个算法，删除重复的数字并返回原始数组中的唯一数字。

例如输入：{4, 8, 4, 1, 1, 2, 9}产出：{4, 8, 1, 2, 9, ?, ?}

一个警告是，预期的算法不应该要求首先对数组进行排序。当元素被移除时，以下元素也必须向前移动。无论如何，元素向前移动的数组尾部的元素值可以忽略不计。

最新情况：必须在原始数组中返回结果，不应使用助手数据结构(例如哈希表)。不过，我想维持秩序是不必要的。

UPDATE 2：对于那些想知道为什么会有这些不切实际的限制的人来说，这是一个面试问题，所有这些限制都是在思考过程中讨论的，看看我怎样才能想出不同的想法。

Answer 1

不如：void&nbsp;rmdup(int&nbsp;*array,&nbsp;int&nbsp;length){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;*current&nbsp;,&nbsp;*end&nbsp;=&nbsp;array&nbsp;+&nbsp;length&nbsp;-&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(&nbsp;current&nbsp;=&nbsp;array&nbsp;+&nbsp;1;&nbsp;array&nbsp;<&nbsp;end;&nbsp;array++,&nbsp;current&nbsp;=&nbsp;array&nbsp;+&nbsp;1&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(&nbsp;current&nbsp;<=&nbsp;end&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(&nbsp;*current&nbsp;==&nbsp;*array&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*current&nbsp;=&nbsp;*end--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}}应该是O(n^2)或更少。

Answer 2

我女朋友提出的一个解决方案是合并排序的变化。唯一的修改是，在合并步骤中，只需忽略重复的值。这个解也是O(N Logn)。在这种方法中，排序/重复删除结合在一起。不过，我不确定这是否有什么区别。