-1

I am trying to remove duplicate elements from my linear array.But i don't want to do it in O(n^2) time complexity.(Because i am using two for loops that will run for n times both in worst case) Is there any way to do this in less time?? Any other approach would be of great help. Thank You!

The Game
  • 62
  • 6
  • 1) If you have a linear array, you should be able to iterate the entire set in O(n) (a single loop). 2) Unless you choose a different data structure (for example, sort the array, or use a hash map) then you have no choice but to iterate the list at least once. – paulsm4 Oct 09 '13 at 21:12
  • possible duplicate of [Removing duplicates from an array in C/C++ in O(n) time](http://stackoverflow.com/questions/7693540/removing-duplicates-from-an-array-in-c-c-in-on-time) – Dennis Meng Oct 09 '13 at 21:14
  • @paulsm4-I have to remove all the duplicate present in the array.So for each element of the array,i have to iterate the complete array.Then it'll take O(n^2). – The Game Oct 09 '13 at 21:17
  • 1) Is the size of the list known in advance? 2) Is there enough memory available: does it fit into memory? 3) must you preserve the original order of the list (minus the deletions) 4) is there any integer value known to be _not_ present on the list (which could be used as a sentinel value) ? – wildplasser Oct 09 '13 at 22:47
  • @wildplasser-Yes the size of array is fixed and known.The order is not important since it is not sorted.Every element is valid integer in the list. – The Game Oct 09 '13 at 23:05

1 Answers1

3

You could sort in O(n log n) and then remove the duplicates in one extra loop, just by checking if any adjacent elements are same. Time: O(n log n)

hazer_drum
  • 253
  • 3
  • 11
  • In addition to this, if you keep track of the original positions in the sort phase (which won't change its O(n log n)-ness), you can then put the remaining elements back in order in O(n)... – twalberg Oct 09 '13 at 21:43