Re-delete

Question

To be honest, this is a hw question.

Question in general:

Introduce an algorithm to remove duplicates in a one-dimensional array using C ++ / Java in O (n) time complexity without additional space. For example, if the input array is {3,5,5,3,7,8,5,8,9,9}, then the output should be {3,5,7,8,9}.

I thought about this for a long time and still could not solve it.

My thoughts:

• I could remove duplicates in O (n) if the array was sorted. But the fastest sorting algorithm that I know has O (n * log (n)) complexity.

• One algorithm that sorts in O (n) is bin or bucket sort. The problem here is that it cannot be implemented without the use of additional space.

• I wonder if this is possible at all.

I did a little research and found nothing new.

Thanks for any help.

PS: I would give him more time if there was no exam tomorrow.

Answer 1

It's really possible, just use in-place sorting in place .

It works for O(kn) , where k is a constant for any standard numeric data type and requires O(1) extra space.

Here is the code:

 #include <stdio.h> #include <stdlib.h> #include <stdint.h> /// in-place 32-bit recursive radix sort void I32R(int32_t *data, uint32_t size, uint32_t nbit) { uint32_t dbgn = (uint32_t)-1, dend = size; while (++dbgn < dend) if (data[dbgn] & nbit) while (dbgn < --dend) if (~data[dend] & nbit) { data[dbgn] ^= data[dend]; data[dend] ^= data[dbgn]; data[dbgn] ^= data[dend]; break; } if ((nbit >>= 1) && (dend > 1)) I32R(data, dend, nbit); if (nbit && (size - dend > 1)) I32R(data + dend, size - dend, nbit); } /// O_t(n) / O_s(1) duplicate remover int32_t dups(int32_t *data, uint32_t size) { int32_t iter, *uniq = data; if (size < 2) return size; for (iter = 0; iter < size; iter++) data[iter] ^= (1 << 31); I32R(data, size, 1 << 31); data[0] ^= (1 << 31); for (iter = 1; iter < size; iter++) if (*uniq != (data[iter] ^= (1 << 31))) *++uniq = data[iter]; return uniq - data + 1; } void parr(int32_t *data, uint32_t size) { for (; size; size--) printf("%4d%s", *data++, (size == 1)? "\n\n" : ", "); } int main() { int32_t iter, size, *data; data = malloc((size = 256) * sizeof(*data)); for (iter = 0; iter < size; iter++) data[iter] = (int8_t)rand() & -3; parr(data, size); parr(data, dups(data, size)); free(data); return 0; } 

NB # 1: inverting the sign bit before sorting, it is necessary that positive numbers become more than negative, since radix sorting only works with unsigned values.

NB # 2: This is just a crude illustration that has never been tested.

NB # 3: oh, this is actually faster than qsort() !

Answer 2

Assuming ar[i]=j , check if ar[j] negative or not if negative deletion of ar[i] else replaces the element ar[j] with -ar[j] .

NOTE. This will only work if all the elements are positive and the elements are inside 0<=elements<array_size .

  for(int i = 0; i < ar.length; i++) { int elem1 = ar[i]; int elem2 = ar[Math.abs(elem1)]; if(elem2 >= 0) { ar[Math.abs(elem1)] = -elem2; } else { //elem1 already exists in an array. remove elem1 or copy distinct elements to another array } }