Without O(n2)
-
go through the array and use a dictonary where object is the array element (or some unique identifer for the items in your array) and int is the count of occurances. go through the array once and add items into the dictonary if it doesn't exist, or increment the count value (the dictonary is a hash so it will be really fast in finding the key/seeing if it exists). after going through the array once, iterate each KeyValuePair in the dictionary and look for any int values greater than 1. your complexity is about O(2n + 1).
-
Hi, in pseudo-C#
List myList=empty;
foreach (element elem in inputcollection) {
if myList contains elem throw new FoundDuplicateException(elem)
else add elem to myList
}
// no duplicates:)
Luc Pattyn
try { [Search CP Articles] [Search CP Forums] [Forum Guidelines] [My Articles] } catch { [Google] }
-
Is this a homework question? 1. Sort the array but keep track of the original positions. 2. Set FOO to size. 3. Compare n with n+1 to find duplicates. If the original positions of the duplicates are less than FOO, set FOO the larger of the original locations. This assumes a number can be repeated once, but it is not hard to modify for multiple occurrences. 4. If FOO == size, there are no duplicates else FOO is the location of the first duplicate. Step 1 is O(nlogn) Step 3 is O(n)