javascript - 仅当 Javascript 中不存在时才追加数组元素

Question

只有在 Javascript 中不存在元素时，我才需要将元素添加到数组中。基本上我将数组视为一个集合。

我需要将数据存储在一个数组中，否则我只会使用一个可以用作集合的对象。

我写了下面的数组原型(prototype)，想听听是否有人知道更好的方法。这是一个 O(n) 插入。我希望执行 O(ln(n)) 插入，但是，我没有看到将元素插入排序数组的简单方法。对于我的应用程序，数组长度将非常小，但我仍然更喜欢遵循公认规则以获得良好算法效率的数组:

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);
}

Answer 1

如果我理解正确，你已经有一个排序数组(如果你没有排序数组，那么你可以使用 Array.sort 方法对你的数据进行排序)现在你想添加一个元素到它，如果它不是已经存在于数组中。我在 google closure library 中提取了二进制插入(使用二进制搜索)方法.相关代码本身看起来像这样，它是 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 = !compareResult;
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // ~left is a shorthand for -left - 1.
  return found ? left : ~left;
};

用法是 binaryInsert(array, value)。这也维护了数组的排序。