StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Hashing is a good idea, it would make the solution O(n) on average</p> <p>Basically you iterate through $arr and make a hash of the entire array and then you compare it against the previous hashes you've seen (this is O(1) using isset(), or O(m) to be precise where m is the number of elements in the inner array). and if there is a collision, you compare the actual array elements. usually a collision means that you've seen that array before and it's a duplicate, but that's not guaranteed. here's some psuedo php that implements this algorithm.</p> <pre><code>function mkhash($array = array()) { $hash = ""; foreach ($array as $element) { $hash .= md5($element); } } $seen = array(); $newArray = array(); foreach($arr as $elementArray) { $hash = mkhash($elementArray); if(!isset($seen[$hash])) { $newArray[] = $elementArray; $seen[$hash] = $elementArray; } else if(count(array_diff($elementArray, $seen[$hash])) > 0) { $newArray[] = $elementArray; //this is true if two different arrays hashed to the same element } } </code></pre> <p>The hashing method is harder to implement, and dealing with collisions properly is tricky, so there's the O(nlogn).</p> <p>The O(nlogn) way of doing this would be to sort the array </p> <pre><code>$arr = array_multisort($arr); //O(nlogn) </code></pre> <p>And then all you would have to do is compare adjacent arrays to see if they are duplicates</p> <p>Of course you can simply use the O(n^2) approach and compare each inner array with every other inner array...</p> <p>EDIT: oh and here's another O(n) idea, you can recursively build a trie using array keys that map to other arrays, so you end up with a m-level deep array where m is the longest inner array you have. Each branch of the trie represents a unique inner array. Of course you would have to write some overhead code to convert the trie back into a 2D array, so you won't see the performance benefit until the cardinality of your input is very large!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload