Efficient removal of duplicates in array-CodePudding

How can duplicates be removed and recorded from an array with the following constraints:

The running time must be at most O(n log n)
The additional memory used must be at most O(n)

The result must fulfil the following:

Duplicates must be moved to the end of the original array
The order of the first occurrence of each unique element must be preserved

For example, from this input:

int A[] = {2,3,7,3,2,11,2,3,1,15};

The result should be similar to this (only the order of duplicates may differ):

 2 3 7 11 1 15     3 3 2 2

CodePudding user response：

As I understand it, the goal is to split an array into two parts: unique elements and duplicates in such a way that the order of the first occurrence of the unique elements is preserved.

Using the the array of the OP as an example:

A={2,3,7,3,2,11,2,3,1,15}

A solution could do the following::

Initialize the helper array with indices 0, ..., n-1:

B={0,1,2,3,4,5,6,7,8,9}

Sort the pairs (A[i],B[i]) using A[i] as key and with a stable sorting algorithm of complexity O(n log n):

A={1,2,2,2,3,3,3,7,11,15}
B={8,0,4,6,1,3,7,2,5, 9}

With n being the size of the array, go through the pairs (A[i],B[i]) and for all duplicates (A[i]==A[i-1]), add n to B[i]:

A={1,2, 2, 2,3, 3, 3,7,11,15}
B={8,0,14,16,1,13,17,2, 5, 9}

Sort the pairs (A[i],B[i]) again, but now using B[i] as key:

A={2,3,7,11,1,15, 3, 2, 2, 3}
B={0,1,2, 5,8, 9,13,14,16,17}

A then contains the desired result.

Steps 1 and 3 are O(n) and steps 2 and 4 can be done in O(n log n), so overall complexity is O(n log n).

Note that this method also preserves the order of duplicates. If you want them sorted, you can assign indices n, n 1, ... in step 3 instead of adding n.

CodePudding user response：

Here is a very important hint: when an algorithm is permitted O(n) extra space, that is not the same as saying it can only use the same amount of memory as the input array!

For example, given the input array int array[] = {2,3,7,3,2,11,2,3,1,15}; (10 elements)
That is a total space of 10 * sizeof(int) bytes.
On a 64-bit machine an int is 8 bytes long, making the array 80 bytes of data.

However, I can use more space for my extra array than just 80 bytes! In fact, I can make a histogram structure that looks like this:

struct histogram
{
  bool   is_used;  // Is this element in use in the histogram?
  int    value;    // The integer value represented by this element
  size_t index;    // The index in the output array of the FIRST instance of the value
  size_t count;    // The number of times the value appears in the source array
};
typedef struct histogram histogram;

And since that is a fixed, finite amount of space, I can feel totally free to allocate n of them!

histogram * new_histogram( size_t size )
{
  return calloc( size, sizeof(struct histogram) );
}

On my machine that’s 240 bytes.

And yes, this absolutely, totally complies with the O(n) extra space requirement! (Because we are only using space for n extra items. Bigger items, yes, but only n of them.)

Goals

So, why make a histogram with all that extra stuff in it?

We are counting duplicates — suggesting that we should be looking at a Counting Sort, and hence, a histogram.
Accept integers in a range beyond [0,n).
^{The example array has 10 items, so our histogram should only have 10 slots. But there are integer values larger than 9.}
Keep all the non-duplicate values in the same order as input
^{So we need to track the index of the first instance of each value in the input array.}

We are obviously not sorting the data, but the basic idea behind a Counting Sort is to build a histogram and then use that histogram to overwrite the array with the ordered elements.

This is a powerful idea. We are going to tweak it.

The Algorithm

Remember that our input array is also our output array! So we will overwrite the array’s input values with our algorithm.

Let’s look at our example again:

2 3 7 3 2 11 2 3 1 15
^{0 1 2 3 4 •5 6 7 8 9}

❶ Build the histogram:

         0   1   2   3   4   5   6   7   8   9 (index in histogram)
used?:  no yes yes yes yes yes  no yes  no  no
value:   0  11   2   3   1  15   0   7   0   0
index:   0   3   0   1   4   5   0   2   0   0
count:   0   1   3   3   1   1   0   1   0   0

^{I used a simple non-negative modulo function to get a hash index into the histogram: abs(value) % histogram_size, then found the first matching or unused entry, again modulo the histogram size. Our histogram has a single collision: 1 and 11 (mod 10) both hash to 1. Since we encountered 11 first it gets stored at index 1 of the histogram, and for 1 we had to seek to the first unused index: 4.}

We can see that the duplicate values all have a count of 2 or more, and all non-duplicate values have a count of 1.

The magic here is the index value. Look at 11. It’s index is 3, not 5. If we look at our desired output we can see why:

2 3 7 11 1 15 2 2 3 3.
^{0 1 2 •3 4 5 6 7 8 9}

The 11 is in index 3 of the output. This is a very simple counting trick when building the histogram. Keep a running index that we only increment when we first add a value to the histogram. This index is where the value should appear in the ouput!

❷ Use the histogram to put the non-duplicate values into the array.

Clearly, anything with a non-zero count appears at least once in the input, so it must also be output.

Here’s where our magic histogram index first helps us. We already know exactly where in the array to put the value!

2 3 7 11 1 15
^{0 1 2 3 4 5 ⟵ index into the array to put the value}

You should take a moment to compare the array output index with the index values stored in the histogram above and convince yourself that it works.

❸ Use the histogram to put the duplicate values into the array.

So, at what index do we start putting duplicates into the array? Do we happen to have some magic index laying around somewhere that could help? From when we built the histogram?

Again stating the obvious, anything with a count greater than 1 is a value with duplicates. For each duplicate, put count-1 copies into the array.

We don’t care what order the duplicates appear, so we’ll just take them in the order they are stored in the histogram.

Complexity

The complexity of a Counting Sort is O(n k): one pass over the input array (to build the histogram) and one pass over the histogram data (to rebuild the array in sorted order).

Our modification is: one pass over the input array (to build the histogram), then one pass over the histogram to build the non-duplicate partition, then one more pass over the histogram to build the duplicates partition. That’s a complexity of O(n 2k).

In both cases it reduces to an O(n) worst-case complexity. In fact, it is also an Ω(n) best-case complexity, making it a Θ(n) complexity — it takes the same processing per element no matter what the input.

Aaaaaahhhh! I gotta code that!!!?

Yep. It is a only a tiny bit more complex than you are used to. Remember, you only need a few things:

An array of integer values (obtained from the user?)
A histogram array
A function to turn an integer value into an index into the histogram
A function that does the three things:
1. Build the histogram from the array
2. Use the histogram to write the non-duplicate values back into the array in the correct spots
3. Use the histogram to write the duplicate values to the end of the array
Ability to print an integer array

Your main() should look something like this:

int main(void)
{
  // Get number of integers to input
  int size = 0;
  scanf( "%d", &n );
  
  // Allocate and get the integers
  int * array = malloc( size );
  for (int n = 0;  n < size;  n  )
    scanf( "%d", &array[n] );
    
  // Partition the array between non-duplicate and duplicate values
  int pivot = partition( array, size );
  
  // Print the results
  print_array( "non-duplicates:", array, pivot );
  print_array( "duplicates:    ", array pivot, size-pivot );
  free( array );
  return 0;
}

Notice the complete lack of input error checking. You can assume that your professor will test your program without inputting hello or anything like that.

You can do this!