小编典典

不使用哈希表从阵列中删除重复项

algorithm

我有一个可能包含重复元素的数组(一个元素的两个以上重复)。我想知道是否有可能找到并删除数组中的重复项:

  • 不使用哈希表(严格要求)
  • 而不使用临时的辅助阵列。没有复杂性的限制。

PS这不是家庭作业问题

在Yahoo技术面试中被问到我的朋友


阅读 277

收藏
2020-07-28

共1个答案

小编典典

对源数组进行排序。查找相等的 连续 元素。(即std::uniqueC ++中的功能)。总复杂度为N lg N,或者如果输入已经排序,则仅为N。

要删除重复项,您还可以线性时间从数组后面的元素复制数组前面的元素。只需保持指向容器新逻辑端的指针,然后在每个步骤将下一个不同的元素复制到该新逻辑端即可。(再次,完全一样std::unique(事实上​​,为什么不下载一个实现std::unique并完全执行它呢?:P))

2020-07-28