AS3, сравнивающий 2 массива

Question

Мне трудно обдумать эту проблему.У меня есть 2 несортированных массива, которые нужно сравнить, массив2 должен содержать все элементы массива1 и массив2 может любое количество дополнительных элементов, не влияя на результат.Я не вижу никаких преимуществ от сортировки массивов и сравнения строковых значений, поскольку массив2 может содержать дополнительную информацию, вызывающую шум.

var array1:Array;
var array2:Array;

// array2 must contain all elements of array1.

var array1:Array = new Array(1, 5, 6, 7);
var array2:Array = new Array(5, 9, 6, 4, 7, 8);
// comparing this should return false (array2 is missing and element from array1)

var array1:Array = new Array(1, 5, 6, 7);
var array2:Array = new Array(5, 9, 6, 4, 7, 1);
// comparing this should return true (array2 has all the elements of array1)

Любая помощь в правильном направлении будет принята с благодарностью.

Answer 1

Наиболее оптимальным решением было бы хеширование элементов из надмножества, чтобы мы могли искать их в постоянном времени.Для этого мы можем использовать Dictionary.

Затем мы перебираем элементы в подмножестве, чтобы определить, существуют ли они в надмножестве.Обратите внимание, что мы записываем количество, это гарантирует, что мы также будем учитывать дубликаты.

Наихудшая сложность этого решения - O (M + N)Однако случай сбоя может завершиться минимумом O (M + 1), поскольку мы вырвемся из второго цикла.

function compare(subSet:Array, superSet:Array):Boolean {

    // Assume true unless proven otherwise
    var retVal:Boolean = true;

    var map:Dictionary = new Dictionary();

    // Place all items from superSet into the dictionary map for constant time
    // lookup, also maintain a count for each item to record duplicates.
    var item:*;
    for each(item in superSet) {
        if(!map[item])
            map[item] = 0;

        // Increment the count for this item in the dictionary
        map[item]++;
    }

    for each(item in subSet) {
        if(map[item])
            // Item exists, decrement count.
            map[item]--;
        else {
            retVal = false;
            break;
        }
    }

    return retVal;
}

Answer 2

Как то так?

function checkContent($needles:Array,$haystack:Array):Boolean
{
    for each(var item:Object in $needles) {
        if($haystack.indexOf(item) == -1) return false;
    }
    return true;
}

Answer 3

Вы также можете рассмотреть возможность размещения ваших объектов (если они являются объектами) в объекте или словаре. Таким образом, вы избегаете ужасного масштабирования при сравнении всех компонентов.

Answer 4

FlexFiend указал вам правильное направление. Словари отлично подходят для таких задач, так как имеют O (1) для поиска / вставки ключа.

function contains(superSet:Array, subSet:Array):Boolean {
    var element:*,
        map:Dictionary = new Dictionary();
    for each (element in superSet) 
        map[element] = true;
    for each (element in subSet)
        if (map[element] != true) return false;
    return true;
}

Это работает в O (M + N), что так же хорошо, как в несортированных массивах.

Answer 5

Посмотрите на Array.every () и Array.indexOf . Однако, возможно, еще лучше прочитать простой учебник по , как массивы работают в ActionScript.