这可以通过一次O(N log N)的算法完成,而且不需要额外的存储空间。
从元素 a[1]
开始,遍历到 a[N]
。在每个阶段 i
,左侧所有元素都包括一个由元素 a[0]
到 a[j]
的排序堆。同时,第二个索引 j
,初始值为0,用于跟踪堆的大小。
检查 a[i]
并将其插入堆中,堆现在占据着元素 a[0]
到 a[j+1]
。当元素被插入时,如果遇到具有相同值的重复元素 a[k]
,则不要将 a[i]
插入堆中(即放弃它);否则将其插入堆中,堆现在增加了一个元素,包含 a[0]
到 a[j+1]
的全部元素,并且将 j
增加1。
继续以这种方式递增 i
,直到检查并将所有数组元素插入堆中,堆最终占用 a[0]
到 a[j]
。 j
是堆的最后一个元素的索引,堆仅包含唯一的元素值。
int algorithm(int[] a, int n)
{
int i, j;
for (j = 0, i = 1; i < n; i++)
{
if (heapInsert(a, j, a[i]))
j++;
}
return j;
}
bool heapInsert(a[], int n, int val)
{
...code omitted for brevity...
if (duplicate element a[k] == val)
return false;
a[k] = val;
return true;
}
查看此示例,这并不完全符合所要求的,因为生成的数组保留了原始元素顺序。但是,如果放宽这个要求,上面的算法应该可以解决问题。