Как ответить на вопрос о дедупликации массива, который поражает интервьюера?

внешний интерфейс JavaScript
Как ответить на вопрос о дедупликации массива, который поражает интервьюера?

Зачем писать эту статью?

  1. Дедупликация массива должна быть интервьюНеобходимыйОдин из вопросов.
  2. Хотя это несложный вопрос, он также может сказать интервьюеру,ширина и глубина, и рассмотреть комплексность проблемы.
  3. В реальной разработке, какой метод мы должны выбрать для дедупликации массива, эта статья расскажет вам.
  4. То, что вы думаете, не обязательно является тем, что вы думаете, интервьюер не просто просит вас повторить массив, он хочет узнать немного больше, включая ваши мысли.

Об авторе: koala, сосредоточив внимание на совместном использовании полного стека технологий Node.js, от JavaScript до Node.js, до серверной базы данных, я желаю вам стать отличным старшим инженером Node.js. [Руководство по развитию программиста] Автор, блог Github с открытым исходным кодомGitHub.com/koala-co Nth…

Как вы отвечаете, когда интервьюер спрашивает?

Первое: я знаю, сколько способов убрать дублирование

двойной цикл

function distinct(arr) {
    for (let i=0, len=arr.length; i<len; i++) {
        for (let j=i+1; j<len; j++) {
            if (arr[i] == arr[j]) {
                arr.splice(j, 1);
                // splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一
                len--;
                j--;
            }
        }
    }
    return arr;
}

Идея: Двойной цикл for — неуклюжий способ, а принцип его реализации прост: сначала определить массив, содержащий первый элемент исходного массива, затем перебрать исходный массив, сравнивая каждый элемент исходного массива с каждым элементом в новом массиве Сравните элементы, добавьте их в новый массив, если они не повторяются, и, наконец, верните новый массив, потому что его временная сложностьO(n^2), если длина массива большая,效率会很低.

Array.filter() плюс Indexof

function distinct(a, b) {
    let arr = a.concat(b);
    return arr.filter((item, index)=> {
        return arr.indexOf(item) === index
    })
}

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

Array.sort() добавляет строку для обхода всплывающих окон (дедупликация соседних элементов)

function distinct(array) {
    var res = [];
    var sortedArray = array.concat().sort();
    var seen;
    for (var i = 0, len = sortedArray.length; i < len; i++) {
        // 如果是第一个元素或者相邻的元素不相同
        if (!i || seen !== sortedArray[i]) {
            res.push(sortedArray[i])
        }
        seen = sortedArray[i];
    }
    return res;
}

Мысль: Метод сортировки массива называетсяsort(), метод sort() движка V8 будет использовать сортировку вставками, когда длина массива меньше или равна 10, и использовать быструю сортировку, когда она больше 10 (функция сортировки подробно описана в моей предыдущей статье о высоких -функции порядка[JS должен знать и должен знать] Подробное объяснение и реальная борьба с функциями высшего порядка). Затем пройти и сравнить соседние элементы по отсортированным результатам (по сути, это строка сравнения пузырьковой сортировки), если они равны, пропустить элемент до конца обхода.

ES6 Установленная дедупликация

function distinct(array) {
   return Array.from(new Set(array));
}

Можно даже еще упростить:

function unique(array) {
    return [...new Set(array)];
}

Можно еще упростить:

let unique = (a) => [...new Set(a)]

Мысль: ES6 предоставляет новую структуру данных Set, особенность структуры Set в том, что значения членов уникальны и нет повторяющихся значений. (Также обратите внимание на этот процесс упрощения)

Пара ключ-значение объекта

function distinct(array) {
    var obj = {};
    return array.filter(function(item, index, array){
        return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
    })
}

Этот метод использует пустой объект Object, и мы сохраняем значение массива как значение ключа объекта, напримерObject[value1] = true, при оценке другого значения, если Object[value2] существует, это означает, что значение повторяется, но обратите внимание на этоobj[typeof item + item] = trueне используется напрямуюobj[item],Потому что Поскольку 123 и «123» разные, непосредственное использование предыдущего метода будет оценивать одно и то же значение, потому что对象的键值只能是字符串, поэтому мы можем использоватьtypeof item + itemУкажите строку в качестве значения ключа, чтобы избежать этой проблемы.

reduce реализует дедупликацию массива объектов

var resources = [
            { name: "张三", age: "18" },
            { name: "张三", age: "19" },
            { name: "张三", age: "20" },
            { name: "李四", age: "19" },
            { name: "王五", age: "20" },
            { name: "赵六", age: "21" }
        ]
     var temp = {};
     resources = resources.reduce((prev, curv) => {
         // 如果临时对象中有这个名字，什么都不做
         if (temp[curv.name]) {
         }
         // 如果临时对象没有就把这个名字加进去，同时把当前的这个对象加入到prev中
         else {
             temp[curv.name] = true;
             prev.push(curv);
         }
         return prev
     }, []);
     console.log("结果", resources);

Этот метод заключается в использовании функции высокого порядка для удаления дубликатов, Здесь вам нужно только обратить внимание на то, что initialValue должен помещать пустой массив [], иначе он не сможет нажать. Подробное объяснение функции уменьшения высшего порядка см. в моей предыдущей статье.[JS должен знать и должен знать] Подробное объяснение и реальная борьба с функциями высшего порядка.

Тогда: Спросите интервьюеру специфичной сцены

(Если то, что вы считали и то, что вы спрашивали, интервьюер не согласился, может, он сам об этом не подумал, просто дал вам дедуплицировать массив, может, этот интервьюер тоже...)

Соображения производительности (вы хотите найти данные с максимальной скоростью?)

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

// distinct.js

let arr1 = Array.from(new Array(100000), (x, index)=>{
    return index
})

let arr2 = Array.from(new Array(50000), (x, index)=>{
    return index+index
})

let start = new Date().getTime()
console.log('开始数组去重')

let arr = a.concat(b);

function distinct(arr) {
    // 数组去重
}

console.log('去重后的长度', distinct(arr).length)

let end = new Date().getTime()
console.log('耗时', end - start)

После удаления различных массивов выше расчет занимает время

Двойной цикл for > Array.filter() плюс indexOf > Array.sort() плюс всплытие обхода одной строки > Дедупликация пары ключ-значение объекта > Установить дедупликацию в ES6

Примечание: Это только результат моего собственного теста. Конкретная ситуация может отличаться от сцены. Например, отсортированный массив может быть дедуплицирован напрямую. Может быть лучше использовать пузырь рядом, чтобы сравнить производительность напрямую. Вы также можете попробовать это сами, и если у вас есть какие-либо вопросы, пожалуйста, обсудите и укажите.

Вопросы совместимости и сценария (содержит ли массив объекты, NaN и т. д.?)

Приходится учитывать, есть ли в этом массиве null, undefined, NaN и объекты.Если появляются оба, то все вышеперечисленные методы дедупликации массива неприменимы.Об этом подробнее поговорим ниже.

Давайте поговорим о разнице между == и ===

===Строгое равенство, сравнивает тип и значение двух значений==Абстрактное равенство, при сравнении сначала будет выполняться преобразование типа, а потом сравниваться значение Если вы хотите узнать больше о процессе конвертации, вы можете прочитать эту статьюРазница между == и === в js

Скажи, какую равную проблему я сказал

let str1 = '123';
let str2 = new String('123');

console.log(str1 == str2); // true
console.log(str1 === str2); // false

console.log(null == null); // true
console.log(null === null); // true

console.log(undefined == undefined); // true
console.log(undefined === undefined); // true

console.log(NaN == NaN); // false
console.log(NaN === NaN); // false

console.log(/a/ == /a/); // false
console.log(/a/ === /a/); // false

console.log({} == {}); // false
console.log({} === {}); // false

Несколько функций дедупликации для контрастов со специальными типами

Небольшое объяснение indexOf и Set:

в приведенном выше кодеconsole.log(NaN === NaN); // false, Нижний слой indexOf использует === для оценки, поэтому элементы NaN не могут быть найдены с помощью indexOf

// demo1
var arr = [1, 2, NaN];
arr.indexOf(NaN); // -1

Set может дедуплицировать типы NaN, и внутренне Set считает, что хотя NaN === NaN является ложным, эти два элемента являются дубликатами.

// demo2
function distinct(array) {
   return Array.from(new Set(array));
}
console.log(unique([NaN, NaN])) // [NaN]

Конкретное сравнение дедупликации

Такой массив в соответствии с приведенным выше методом взвешивания сравнения:

var array = [1, 1, '1', '1', null, null, undefined, undefined, new String('1'), new String('1'), /a/, /a/, NaN, NaN];
метод результат иллюстрировать
двойной цикл [1, "1", null, undefined, String, String, /a/, /a/, NaN, NaN] Объекты и NaN не дедуплицируются
Array.sort() плюс строка обхода [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] NaN тяжелые объекты, а не номер 1, не становятся тяжелыми
Array.filter() плюс indexOf [1, "1", null, undefined, String, String, /a/, /a/] Объекты не дедуплицированы. NaN будет игнорироваться.
Значение ключа объекта [1, "1", null, undefined, String, /a/, NaN] дедуплицировать все
Настроить дедупликацию в ES6 [1, "1", null, undefined, String, String, /a/, /a/, NaN] Объекты не дедуплицируются, дедупликация NaN

Соображения памяти (вы хотите, чтобы самая низкая сложность пространства в процессе дедупликации?)

Хотя говорят, что для движка V8 соображения памяти стали менее важными, и когда объем данных действительно велик, дедупликация вообще обрабатывается в фоновом режиме. Тем не менее, мы также不能放过任何一个可以证明自己优秀的, или подумайте об этом, хе-хе.

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

Но сложность пространства дедупликации объекта является самой высокой с момента открытия объекта, несколько других способов не открывают новые пространства, из более глубокого источника, который нужно изучить, просто чтобы показать всем здесь, чтобы ответить, когда вы также можете принять во внимание时间复杂度а также空间复杂度.

добавить ещеНепонимание, некоторые друзья подумают, чтоArray.filter()ДобавитьindexOfВременная сложность этого методаO(n), не совсем, я так думаюO(n^2). потому чтоindexOfфункция, исходный код фактически проходит цикл for. Конкретная реализация выглядит следующим образом

String.prototype.indexOf = function(s) {
    for (var i = 0; i < this.length - s.length; i++) {
        if (this.charAt(i) === s.charAt(0) &&
            this.substring(i, s.length) === s) {
            return i;
        }
    }
    return -1;
};

Дополнительное описание сторонней библиотеки lodash

Как lodash реализует дедупликацию

просто скажиlodashизuniqИсходный код реализации метода.

Поведение этого метода такое же, как результат дедупликации с помощью Set.

Когда длина массива больше или равна200, создастSet и воляSetПреобразование в массив для дедупликации (реализация отсутствия Set не делает анализ). Если длина массива меньше200, будет использоваться схема дедупликации, аналогичная вышеупомянутому двойному циклу,Кроме того, он также будет выполнять дедупликацию NaN..

Суммировать

Чтобы ответить на вопросы интервьюера во время интервью, но вы можете скомпилировать код, чтобы получить правильный результат, правильно также содержит понимание проблемы, также необходимо рассмотреть следующие вопросы:

  • оптимизация
  • спецификация кода
  • Отказоустойчивость

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

Справочная статья

Некоторые пояснения функций в MDN

Углубленный анализ дедупликации массива

Дедупликация массива тем JavaScript

Сводка по обучению алгоритму сортировки

Подписывайтесь на меня

  • Добро пожаловать, чтобы добавить меня в WeChat [coder_qi], пригласить вас в техническую группу, долгосрочный обмен и изучение...
  • Добро пожаловать, чтобы обратить внимание на «Руководство по развитию программиста на севере», общедоступную учетную запись, которая поможет вам расти с душой...

Оригинальные статьи серии Node

Глубокое понимание процессов и потоков в Node.js

Если вы хотите изучить Node.js, сначала необходимо понять поток.

Когда требуется, вы действительно понимаете разницу между экспортом и модулем.экспорт?

В статье об интерпретации исходного кода подробно рассматривается модуль Events.

Node.js расширенное расширенное изучение файлового модуля fs

Категории