Найти повторяющийся массив в массиве

Question

Учитывая массив массивов, каков был бы эффективный способ идентификации дублирующего элемента?

var array = [ 
    [ 
    11.31866455078125, 
    44.53836644772605 
    ], 
    [      // <-- Here's the duplicate 
    11.31866455078125, 
    44.53836644772605 
    ], 
    [ 
    11.371536254882812, 
    44.53836644772605 
    ], 
    [ 
    11.371536254882812, 
    44.50140292110874 
    ] 
] 

Я работал над этим с lodash как обслуживаемый зависимость, и я, как только вернуть «уникальный» список, используя _.uniqWith и _.isEqual:

_.uniqWith(array,_.isEqual) 

С дало бы " уникальная»версия списка:

[ 
    [ 11.31866455078125, 44.53836644772605 ], 
    [ 11.371536254882812, 44.53836644772605 ], 
    [ 11.371536254882812, 44.50140292110874 ] 
] 

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

Это действительно покрыто библиотекой lodash некоторой комбинацией методов, которые мне не хватает? Или мне просто придется жить с пишущими циклами для сравнения элементов.

Возможно, это просто переусердствовало, поэтому свежие глаза на проблему были бы приветствуются.

Попытка не переписать функции, если есть библиотека методы, которые подходят, так что я в основном я застрял с:

1. Возвращение только дубликат или, по крайней мере, разница в сравнении с «уникальным списком».

2. В основном идентифицируется «индекс» массива в массиве. Хотя я полагаю, что это может быть уменьшение фильтра с _.isEqual, как только будет идентифицирован дублирующий элемент.

Попытка также, чтобы избежать создания объекта Hash/Карта и подсчета вхождений ключей и здесь, или по крайней мере не в качестве отдельного объекта, а также то, что может быть сделано функционально «в линию».

Answer 1

Lodash предоставляет множество полезных функций для достижения первого дубликата индекса.
Использования _.findIndex() и _.isEqual() следующего кода будет найти первый индекс дубликата:

var duplicateIndex = _.findIndex(array, function(value, index, collection) { 
    var equal = _.isEqual.bind(undefined, value); 
    return _.findIndex(collection.slice(0, index), equal) !== -1; 
}); 

или немного быстрее, но более подробный:

var duplicateIndex = _.findIndex(array, function(value, index, collection) { 
    var equal = _.isEqual.bind(undefined, value); 
    return _.findIndex(collection, function(val, ind) { 
    return ind < index && equal(val); 
    }) !== -1; 
}); 

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

Answer 2

Вы можете просто использовать простой ПР»JavaScript, чтобы сделать это, это не так сложно, вот моя реализация

for (var i = 0; i < array.length; i++) { 
    for (var j = i + 1; j < array.length; j++) { 

    // quick elimination by comparing subarray lengths 
    if (array[i].length !== array[j].length) { 
     continue; 
    } 
    // look for dupes 
    var dupe = true; 
    for (var k = 0; k < array[i].length; k++) { 
     if (array[i][k] !== array[j][k]) { 
     dupe = false; 
     break; 
     } 
    } 
    // if a dupe then print 
    if (dupe) { 
     console.debug("%d is a dupe", j); 
    } 
    } 
} 

Хорошая часть об этой реализации является то, что он напечатает вам несколько раз, что массив в индекс является обманом для нескольких обманов, вы можете использовать этот факт, чтобы подсчитывать ваших обманов в каждом индексе!

Это действительно очень эффективный способ сделать это, потому что внутренний цикл for (j) всегда исходит из следующего положения внешнего контура (i). так что вы половину проверки.

А вот plunk

Answer 3

Я не знаю, как это сделать, кроме как просто написать алгоритм самостоятельно. И этот ответ, и другие отправленные из них являются не очень эффективными, но должно быть хорошо:

function findIndex(array, startingIndex, value) { 
    var predicate = _.partial(_.isEqual, value); 
    var arraySubset = array.slice(startingIndex+1); 
    var index = arraySubset.findIndex(predicate); 
    return index === -1 ? index : index+startingIndex+1; 
} 

function findDuplicates(array) { 
    return array.map((value, index) => { 
    return { 
     value, 
     index: findIndex(array, index, value) 
    }; 
    }).filter(info => info.index !== -1); 
} 

findDuplicates([1, 2, 3, 4, 1, [ 3 ], [ 4 ], [ 3 ] ]); 

// [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ] // [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ] 

Это в основном создает карту массива, вызывая .findIndex() на оставшейся части массива, записывая индекс любых дубликатов, возвращающих информацию о каждом элементе с дубликатом и том, что является индексом дубликата.

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

Answer 4

Вот такой подход, который использует uniqWith() и difference():

_.indexOf(array, _.head(_.difference(array, _.uniqWith(array, _.isEqual)))); 

Основная идея:

1. Использование uniqWith() для удаления дубликатов из array.
2. Используйте difference(), чтобы сравнить array с дублирующейся версией. Это дает нам массив дубликатов.
3. Используйте head(), чтобы получить первый элемент массива. Это дубликат, который нас интересует.
4. Используйте indexOf(), чтобы найти индекс дубликата, в данном случае это 1.

Однако, если вам нужен индекс оригинального, а не это дублировать, мы должны внести некоторые коррективы:

var duplicate = _.head(_.difference(array, _.uniqWith(array, _.isEqual))); 
_.findIndex(array, _.unary(_.partial(_.isEqual, duplicate))); 

Мы все еще используем uniqWith() и difference() к найдите duplicate. Но теперь мы используем findIndex(), чтобы получить индекс. Причина в том, что нам нужно использовать isEqual(), чтобы найти первое положение дубликата, а не второе. Мы строим предикат с использованием partial() и unary(). Результат на этот раз: 0.

Answer 5

Я считаю, что создание LUT является одним из наиболее эффективных способов, позволяющих делать сравнения. Следующий метод создает LUT, используя Array.prototype.reduce() и в конечном итоге мутирует исходный массив, удаляя не только один, но и все повторяющиеся элементы независимо от того, сколько их там.

var arr = [ 
 
    [ 
 
    11.31866455078125, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.31866455078125, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.371536254882812, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.371536254882812, 
 
    44.50140292110874 
 
    ] 
 
]; 
 
arr.reduce((p,c,i)=> { var prop = c[0]+"" + c[1]+""; 
 
         p[prop] === void 0 ? p[prop] = i : p.dups.push(i); 
 
         return p; 
 
        },{dups:[]}).dups.reverse().forEach(i => arr.splice(i,1)) 
 

 
document.write('<pre>' + JSON.stringify(arr, 0, 2) + '</pre>');

Однако, если вы хотели бы иметь новый массив, сохраняя оригинал, то, очевидно, было бы гораздо быстрее процедура.