Блог

Мне нужно добавить элемент в массив, только если его еще нет в Javascript. По сути, я рассматриваю массив как набор.

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

Я написал следующий прототип массива и хотел услышать, знает ли кто-нибудь лучший способ. Это O (n) вставка. Я надеялся выполнить O (ln (n)) insert, однако я не видел простого способа вставить элемент в отсортированный массив. Для моих приложений длина массива будет очень маленькой, но я бы все же предпочел что-то, что подчинялось принятым правилам для хорошей эффективности алгоритма:

 Array.prototype.push_if_not_duplicate = function(new_element){
    for( var i=0; i<this.length; i   ){
        // Don't add if element is already found
        if( this[i] == new_element ){
            return this.length;
        }
    }
    // add new element
    return this.push(new_element);
}
  

Если я правильно понимаю, у вас уже есть отсортированный массив (если у вас нет отсортированного массива, вы можете использовать метод Array.sort для сортировки ваших данных), и теперь вы хотите добавить к нему элемент, если он еще не присутствует в массиве. Я извлек метод двоичной вставки (который использует двоичный поиск) в библиотеке закрытия Google. Сам соответствующий код будет выглядеть примерно так, и это операция O (log n), потому что двоичный поиск равен O (log n) .

 function binaryInsert(array, value) {
  var index = binarySearch(array, value);
  if (index < 0) {
    array.splice(-(index   1), 0, value);
    return true;
  }
  return false;
};

function binarySearch(arr, value) {
  var left = 0;  // inclusive
  var right = arr.length;  // exclusive
  var found;
  while (left < right) {
    var middle = (left   right) >> 1;

    var compareResult = value > arr[middle] ? 1 : value < arr[middle] ? -1 : 0;
    if (compareResult > 0) {
      left = middle   1;
    } else {
      right = middle;
      // We are looking for the lowest index so we can't return immediately.
      found = !compareResu<
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // ~left is a shorthand for -left - 1.
  return found ? left : ~left;
};
  

Используется binaryInsert(массив, значение). Это также поддерживает сортировку массива.

Удалил мой другой ответ, потому что я пропустил тот факт, что массив отсортирован.

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

Весь алгоритм можно улучшить, используя алгоритм «разделяй и властвуй». Выберите элемент в середине массива, сравните с новым элементом и продолжайте, пока не найдете место для вставки. Это будет немного быстрее, чем ваш приведенный выше алгоритм, и впоследствии не потребует сортировки.

Если вам нужна помощь в разработке алгоритма, не стесняйтесь спрашивать.

Раньше я создавал (простой и неполный) Set тип, подобный этому:

 var Set = function (hashCodeGenerator) {
    this.hashCode = hashCodeGenerator;
    this.set = {};
    this.elements = [];
};
Set.prototype = {
  add: function (element) {
    var hashCode = this.hashCode(element);
    if (this.set[hashCode]) return false;
    this.set[hashCode] = true;
    this.elements.push(element);
    return true;
  },
  get: function (element) {
    var hashCode = this.hashCode(element);
    return this.set[hashCode];
  },
  getElements: function () { return this.elements; }
};
  

Вам просто нужно найти хорошую hashCodeGenerator функцию для ваших объектов. Если ваши объекты являются примитивами, эта функция может вернуть сам объект. Затем вы можете получить доступ к элементам набора в форме массива из средства getElements доступа. Вставки равны O (1). Требования к пространству — O (2n).

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

В Википедии есть отличное объяснение.