tag:blogger.com,1999:blog-6314876008291942531.post5928130569185209350..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Unique elementsUnknownnoreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6314876008291942531.post-57650626559669486112010-06-14T08:12:47.184-07:002010-06-14T08:12:47.184-07:00In the case that the values of the input array are...In the case that the values of the input array are < size of array, another solution could be:<br /><br />for (int i = 0; i < a.length; i++) {<br /><br /> if (a[i] == -1) continue;<br /> if (i == a[i]) continue;<br /><br /> if (a[i] == a[a[i]]) {<br /> a[i] = -1;<br /> }<br /> else {<br /> swap(i, a[i]);<br /> i = i - 1;<br /> }<br />}Claudio Corsihttps://www.blogger.com/profile/13435215356783747956noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-41513430006016157492010-06-14T06:26:41.469-07:002010-06-14T06:26:41.469-07:00Some assumptions:
1) if the input array is sorted...Some assumptions:<br /><br />1) if the input array is sorted, then you can solve the problem with a single pass, skipping duplicated that are in sequence<br /><br />2) if the elements are between 0 and k, take an array C, and fill it as follows: C[I[n]] = C[I[n]]]++, where I is the input array and C is initialized to 0s.<br /><br />C will have k slots.<br /><br />Now, for each value in I you have a counting of the number of times it appears, so you could delete (set to null) the slots in A having values such that C[A[i]] > 1 (i : 0 to size(A)).<br /><br />This solution is similar to the one proposed by Danny, where the dictionary is the array C and the hash function is given by A[i] (with no costs to be computed).Claudio Corsihttps://www.blogger.com/profile/13435215356783747956noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-2567923994032780402010-06-13T11:19:18.586-07:002010-06-13T11:19:18.586-07:00hashset = new HashSet
array foreach {
insert int...hashset = new HashSet<br />array foreach {<br /> insert into hashset _<br />}<br />return hashsetrobsonhttps://www.blogger.com/profile/05635784812794700266noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-48826547295500635352010-06-10T09:50:44.361-07:002010-06-10T09:50:44.361-07:00How about using a bloom filter (for very large n)?...How about using a bloom filter (for very large n)? On one parse, remove already hashed elements. space complexity is O(1), the size of the filter.sinusoidhttps://www.blogger.com/profile/08742829199732307797noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-38831877722718570702010-06-09T12:37:13.458-07:002010-06-09T12:37:13.458-07:00Is removing the element of an array O(1)? You can ...Is removing the element of an array O(1)? You can also use a HashSet instead of a Map and go through the array just once, adding the elements into the hashset or removing them from the array if they already exist in the HashSet.noumenohttps://www.blogger.com/profile/16579246954067052291noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-47050441411320878562010-06-08T15:13:11.872-07:002010-06-08T15:13:11.872-07:00Employ a hash table with 2n slots and use linear (...Employ a hash table with 2n slots and use linear (or quadratic) probing for colission resolution.Leohttps://www.blogger.com/profile/17742002772935000604noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-18783455868071931112010-06-07T17:20:57.948-07:002010-06-07T17:20:57.948-07:00If you assume 'n' to be asymptotically lar...If you assume 'n' to be asymptotically larger than the number of digits present in the largest number in the array, one could potentially use radix sort to sort these numbers in O(kn) time where k is number of digits in the largest number. It is then O(n) to remove duplicates by walking the sorted array; thus overall running time is still O(n)? Would that be an accceptable solution?Venkateshhttps://www.blogger.com/profile/15893132887136527161noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-11999588677861406992010-06-07T15:16:29.208-07:002010-06-07T15:16:29.208-07:00Dictionaries usually have O(log n) performance...Dictionaries usually have O(log n) performance...ReaderThinkerhttps://www.blogger.com/profile/00843921662893708861noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-87894384548651673912010-06-06T01:28:24.949-07:002010-06-06T01:28:24.949-07:00Instead of boolean, you can hold the index of the ...Instead of boolean, you can hold the index of the first location of this element.<br />If you find an element that is already in the dictionary, remove it and remove the element in the stored location and mark it non-unique element. Next time you find this element only remove the one you just found.Dannyhttps://www.blogger.com/profile/01182301752254944419noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-15611441921841535412010-06-06T00:11:53.015-07:002010-06-06T00:11:53.015-07:00anything better?anything better?codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-26215458561282056082010-06-05T23:58:56.844-07:002010-06-05T23:58:56.844-07:00Hold a dictionary from element -> boolean
Go ov...Hold a dictionary from element -> boolean<br />Go over the array. <br />Mark each element in the dictionary as true if this is its first appearance. <br />Mark it as false if non-unique (i.e., element already existed in the dictionary)<br />Go over the array again and remove each element with false in the dictionary.Dannyhttps://www.blogger.com/profile/01182301752254944419noreply@blogger.com