javascript - 如何分配尚未分配的尽可能低的数字

Question

我正在做的是动态创建元素并将它们附加到页面。这些元素需要有一个 id，因此我在创建元素时为每个元素分配了一个数字 id。但是，元素可以并且将会以非线性方式被删除，因此您最终可能会在值之间产生差距，例如...

一个假设场景:1、3、4、5、16 ，22。

在上面的例子中，如果我要创建一个元素，我想指定 2 作为它的 id。

另一个假设场景:3、4、5。

在这种情况下，1 应指定为 id。

我已经编写了下面的代码，应该可以正常工作，但我觉得它不必要地复杂。 有人知道如何改进它吗？!

const divs = element.getElementsByTagName('div')
for (let i = 0; i < divs.length; i++) {
  if (i > 0 && Number(divs[i].id) > Number(divs[i-1].id)+1 ) {
    return Number(divs[i-1].id)+1
    break
  } else if (i === divs.length-1) {
    return Number(divs[divs.length-1].id)+1
  } else if (Number(divs[0].id) > 1) {
    return 1
    break
  } else if (divs.length === 1 && Number(divs[0].id) === 1) {
    return 2
  } else if (divs.length === 1 && Number(divs[0].id) !== 1) {
    return 1
  }
}

我选择采纳 elsyr 的建议并跟踪 ID。这将使我能够实现以下代码，这是在特定情况下的最佳选择。

const lowestNum = lowestId()
div.id = lowestNum
numericalIds[lowestNum-1] = lowestNum

function lowestId(){
  for (let i = 0; i < numericalIds.length; i++) {
    if (!numericalIds[i]) {
      return i+1
    } else if (i === numericalIds.length-1) {
      return numericalIds[numericalIds.length-1]+1
    }
  }
  return 1
}

我只需要在元素从页面中删除之前更新数组即可。

numericalIds[/*numerical value of id*/-1] = 0 // or null or undefined

这将始终使用尚未分配且不小于 1 的最小数值创建 ID。

Answer 1

如果我们谈论算法复杂性，您的实现是 O(n) 最坏情况。如果您想做得更好，您可能需要使用更合适的数据结构来存储您的 ID。

有点像 priority queue/min heap会好一点，但你也说过你相对简单的循环已经太复杂了——你必须愿意找到一个好的库或自己编写它们，而这不一定更简单。我不会在这里写一个实现，因为我认为这超出了像这样的帖子的范围。

假设我们有“释放”ID 和“占用”ID 的概念，当我们“释放”一个 ID 时调用 insert，然后调用 pop当我们“取”一个 ID 时，使用上面的 DS 允许我们将最坏情况的复杂性降低到 O(logn)，而不是遍历整个数组。它看起来像这样(省略了实际的 minHeap 实现):

function takeLowestAvailableID() {
    return minHeap.pop();
}

function freeID(int freed) {
    minHeap.push(freed);
}

请注意，这些是最坏的情况 运行时的复杂性，我们甚至还没有讨论内存方面的考虑

如果不进一步了解您的应用程序以及您的数据是如何产生的，就很难提出一个包罗万象的建议。如果您只存储 1-50 和 99% 的 ID，您的应用程序只会使用 1-10，那么坚持使用您现在拥有的功能可能是值得的。