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

Question

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

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

我编写了以下数组原型，想听听是否有人知道更好的方法。这是一个 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 方法对数据进行排序），现在您想向其中添加一个元素（如果该元素尚不存在）数组。我在 二进制插入（使用二进制搜索）方法rel="nofollow">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 = !compareResult;
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // ~left is a shorthand for -left - 1.
  return found ? left : ~left;
};

用法是binaryInsert（数组，值）。这也保持了数组的排序。

Answer 2

删除了我的其他答案，因为我错过了数组已排序的事实。

您编写的算法会遍历数组中的每个元素，如果没有匹配项，则会在末尾附加新元素。我认为这意味着您之后正在运行另一种类型。

可以通过使用分治算法来改进整个算法。选择数组中间的一个元素，与新元素进行比较，然后继续，直到找到插入的位置。它会比上面的算法稍快，并且之后不需要排序。

如果您需要帮助制定算法，请随时询问。

Answer 3

我之前已经创建了一个（简单且不完整的）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)。

Answer 4

如果您的数组是二叉树，则可以通过将新元素放在末尾并将其冒泡到位来以 O(log n) 进行插入。执行重复项检查也需要 O(log n) 时间。

维基百科有很好的解释。