Эффективный алгоритм для разницы массива и известной подпоследовательности? - PullRequest
Новая
       26

Эффективный алгоритм для разницы массива и известной подпоследовательности?

3 голосов
/ 29 декабря 2011

Я передаю массив в библиотечную функцию, которая возвращает массив, который является подпоследовательностью входного массива. То есть порядки первого и второго массива идентичны, но во втором массиве может отсутствовать любое количество элементов первого массива. В любом массиве не будет дубликатов!

Я хочу затем создать новый массив всех элементов, которые были на входе, но не на выходе функции.

По какой-то причине, хотя это звучит тривиально, я продолжаю понимать это неправильно, особенно на концах массивов, которые кажутся.

Пример 1 (типичный):

входной массив a: 

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, ios, app, tlv, lcy ]

входной массив b: 

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, tlv, lcy ]

выходной массив "diff": 

[ ios, app ]

Пример 2 (минимальный, выявляет некоторые ошибки, когда разница находится в конце строк):

входной массив a: 

[ usa ]

входной массив b: 

[ ]

выходной массив "diff": 

[ usa ]

(Я собираюсь реализовать его в JavaScript / jQuery, но меня больше интересует универсальный алгоритм в псевдокоде, поскольку я на самом деле буду иметь дело с массивами объектов. Поэтому, пожалуйста, я ищу алгоритмы, которые специально используют индексирование массива, а не указатели, как в C / C ++)

Ответы [ 3 ]

3 голосов
/ 29 декабря 2011

Поскольку второй массив b является подмножеством первого массива a в том же порядке, вы можете идти параллельно, сравнивать текущие значения и принимать текущее значение a , если оно отличается от текущего значения b : 

var a = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','ios','app','tlv','lcy'],
    b = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','tlv','lcy'],
    diff = [];
var i=0, j=0, n=a.length, m=b.length;
while (i<n && j<m) {
    if (a[i] !== b[j]) {
        diff.push(a[i]);
    } else {
        j++;
    }
    i++;
}
while (i<n) {
    diff.push(a[i++]);
}

или если вы предпочитаете только один цикл while: 

// …
while (i<n) {
    if (j<m && a[i] === b[j]) {
        j++;
    } else {
        diff.push(a[i]);
    }
    i++;
}
0 голосов
/ 29 декабря 2011

У вас есть гарантированный порядок наложения на ваши массивы?Если это так, это должно быть относительно просто сделать что-то вроде: 

# our inputs are array1 and array2, array2 is the one with 0 or more missing elements
ix1 = 0
ix2 = 0
diff = new array
while ix2 < length(array2)
  while (ix1 < length(array1)) and (array1[ix1] != array2[ix2])
     add array1[ix1] to diff
     ix1 = ix1 + 1
  ix1 = ix1 + 1
  ix2 = ix2 + i

return diff

Если у вас нет порядка, вы можете либо навязать один (отсортировать оба массива), либо использовать хеш-таблицу. 

hash = new hash
diff = new array

for each element in array1
  hash[element] = 1

for each element in array2
  hash[element] = hash[element] + 1

for each key in hash
  if hash[key] == 1
    add hash[key] to diff

Оба из них должны выполняться (примерно) в O (n), если (и только если) добавление элемента в массив равно O (1) (если вы удваиваете размер результирующего массива каждый разоно заполняется, по крайней мере асимптотически O (1)).

0 голосов
/ 29 декабря 2011

В Java я, вероятно, сделал бы что-то подобное, если бы я использовал Arrays. Вам придется перебрать все ваши объекты, которые вы вернете, и вам придется сравнить их со всеми теми вещами, которые вы отправили, так что в худшем случае у вас будет сложность O (n ^ 2), я верю, но вы, вероятно, можете улучшить это, отсортировав список, который вы отправляете, и использовать указатели, чтобы проверить каждую позицию (но так как вы не хотите использовать указатели, я опускаю этот образец), тогда вы можете сравнить это в O (n). 

public void doYourJob(){
        Object[] allObjects = new Object[10]; //hold all original values
        Object[] recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one
        Object[] missingArray = new Object[allObjects.length - recivedArray.length];
        for(Object inObj : allObjects){
            boolean foundObject = false;
            for(Object obj : recivedArray){
                if(inObj.equals(obj)){
                    foundObject = true;
                    break;
                }
            }
            if(!foundObject)
                missingArray add inObj //add the missing object. This is not correct java code. =)
        }
    }

Если бы я был вслух использовать что-то из интерфейса Collection, то это было бы намного проще, поскольку вы можете использовать метод myArray.contains ().

со списками вместо 

public void doYourJob(){
        List<Object> allObjects = new ArrayList<Object>(); //hold all original values
        List<Object>  recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one
        List<Object>  missingArray = new ArrayList<Object>();
        for(Object inObj : allObjects){
            if(!recivedArray.contains(inObj))
                missingArray.add(inObj);
        }
    }
...