Unique elements in an array - Algorithm Geeks

I need to find and remove repeated elements from a linear collection. there are very few repeats and each element it not repeated more than twice. Is there an algorithm with faster than O(n^2) run time to achieve this?

Version:

Latest 3 messages about this page (17 total) - view full discussion

Dec 20 2007 by Dave

Quicksort has an _average_ time of O(n log n) for random data, but it can degenerate to O(n^2) for certain initial orderings. Thus, your statement that it will take O(n log n) time is not justified. That is why it has been suggested to use a heapsort or mergesort, both of which are O(n log n).

Dec 20 2007 by Bookpet

I think this method will solve the problem: 1). first, sort the linear array using quick sort method, it will take O(n(logn)) time 2).second, scan the sorted linear array: Array[nLen] //sorted data Array. T tSameData; int iNum; int i, j, k, iLast = nLen; //nLen is the length of the array. for (i=0; i<iLast; i++)

Dec 20 2007 by Bookpet

I think this method will solve the problem: 1). first, sort the linear array using quick sort method, it will take n(logn) time 2).second, scan the sorted linear array: Array[nLen] //sorted data Array. T tSameData; int iNum; int i, j, k, iLast = nLen; //nLen is the length of the array. for (i=0; i<iLast; i++)

14 more messages »

Report this page

Une démonstration plus détaillé_eng.pdf	Jul 19
hfile.htm (2)	Mar 12
hfile.htm	Mar 11
rKKUP.htm	Sep 17
AlgorithmQuestionSolution.pdf	Mar 25
Find_hamming_wo_boost.cpp	Dec 7
Find_hamming.cpp (2)	Dec 7
Find_nums_by_sums.cpp	Nov 7
Find_hamming.cpp	Oct 31
NN_max_matrix.cpp	Oct 12