在线性时间内从阵列中删除重复项，而无需额外的阵列 [英] Remove duplicates from array in linear time and without extra arrays

问题描述

我们有一个数组，并且未排序.我们知道范围是[0，n].

We have an array and it is unsorted. We know the range is [0,n].

我们要删除重复项，但是我们不能使用额外的数组，并且必须在线性时间内运行.

We want to remove duplicates but we cannot use extra arrays and it must run in linear time.

有什么想法吗?只是为了澄清，这不是为了功课！

Any ideas? Just to clarify, this is not for homework!

推荐答案

如果整数限制为0到n，则可以遍历数组，并按其索引放置数字.每次替换数字时，请使用以前存在的值并将其移动到应有的位置.例如，假设我们有一个大小为8的数组:

If the integers are limited 0 to n, you can move through the array, placing numbers by their indices. Every time you replace a number, take the value that used to be there and move it to where it should be. For instance, let's say we have an array of size 8:

-----------------
|3|6|3|4|5|1|7|7|
-----------------
 S

这里S是我们的起点，我们将使用C跟踪下面的当前"索引. 我们从索引0开始，然后将3移到索引3的位置，这里是4.在临时变量中保存4.

Where S is our starting point, and we'll use C to keep track of our "current" index below. We start with index 0, and move 3 to the 3 index spot, where 4 is. Save 4 in a temp var.

-----------------
|X|6|3|3|5|1|7|7|   Saved 4 
-----------------  
 S     C

然后将4放入索引4，保存以前的5.

We then put 4 in the index 4, saving what used to be there, 5.

-----------------
|X|6|3|3|4|1|7|7|   Saved 5
-----------------
 S       C

继续前进

-----------------
|X|6|3|3|4|5|7|7|   Saved 1
-----------------
 S         C

-----------------
|X|1|3|3|4|5|7|7|   Saved 6
-----------------
 S C

-----------------
|X|1|3|3|4|5|6|7|   Saved 7    
-----------------
 S           C 

当我们尝试替换7时，我们看到了冲突，因此我们只是不放置它.然后，我们从起始索引S继续，将其递增1:

When we try to replace 7, we see a conflict, so we simply don't place it. We then continue from the starting index S, increment it by 1:

-----------------
|X|1|3|3|4|5|6|7| 
-----------------  
   S           

这里1很好，3需要移动

1 is fine here, 3 needs to move

-----------------
|X|1|X|3|4|5|6|7|
-----------------
     S

但是3是重复的，因此我们将其丢弃并继续遍历数组的其余部分.

But 3 is a duplicate, so we throw it away and keep iterating through the rest of the array.

因此，基本上，我们将每个条目最多移动1次，并遍历整个数组.那是O(2n)= O(n)

So basically, we move each entry at most 1 time, and iterate through the entire array. That's O(2n) = O(n)

这篇关于在线性时间内从阵列中删除重复项，而无需额外的阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！