actionscript 3 - Flash as3 How do I remove duplicates in an array?

Question

Hi I just have an array of names (strings) in flash, and I want to make sure that any duplicates from the array are removed, or at least that a function is performed only once per reocurring value in the array.

Answer 1

Many ways. You can sort the array and iterate over it ignoring entries that match the previous iteration. Or you can use indexOf() to search for duplicates. Or you can take one pass over the array, build a dictionary keyed on the strings (and just ignore keys that already have an entry).

Here is the Dictionary way, memory cost of 1 boolean per unique entry, easy on memory for when you expect a lot of dupes, and fast. If you have relatively few dupes, the sort + culling of consecutive dupes is probably more efficient

import flash.utils.Dictionary;

var array:Array = ["harry","potter","ron","harry","snape","ginny","ron"];
var dict:Dictionary = new Dictionary();

for (var i:int = array.length-1; i>=0; --i)
{
    var str:String = array[i] as String;
    trace(str);
    if (!dict[str])
    {
        dict[str] = true;
    }
    else
    {
        array.splice(i,1);
    }
}

dict = null;


trace(array);

Here's a sorting way, but note: THIS DOES NOT PRESERVE ORDER! You didn't say if that matters. But because it's using quicksort, it does tend to have O(N log N) performance plus the one extra pass, unless of course your data is a pathological case.

var array:Array = ["harry","potter","ron","harry","ron","snape","ginny","ron"];

array.sort();
trace(array);

for (var i:int = array.length-1; i>0; --i)
{
    if (array[i]===array[i-1])
    {
        array.splice(i,1);
    }
}


trace(array);

In addition to not specifying whether order matters, you did not say if it matters which of the dupes is left: the one at the lowest index, or the last one found. If that matters, you will need to re-order my dictionary example to run in the opposite direction. I started at the end because that makes it OK to do a splice without invalidating the loop count (i.e. by changing the array.length during the looping) If order matters, loop in the usual forward direction and copy out the first occurrence of each string to a new array, or modify the loop counter like this. This is probably the technique I'd use, because it preserves order and keeps the first-encountered instance of each string:

import flash.utils.Dictionary;

var array:Array = ["harry","potter","ron","harry","snape","ginny","ron"];
var dict:Dictionary = new Dictionary();

var len:int = array.length;
for (var i:int = 0; i<len; ++i)
{
    var str:String = array[i] as String;
    if (!dict[str])
    {
        dict[str] = true;
    }
    else
    {
        array.splice(i,1);
        i--; len--;
    }
}

dict = null;


trace(array);