如何分配尚未分配的最低编号

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，当我们'获取'ID时调用pop，使用上面的DS可以让我们放弃最坏的ID案例复杂性下降到O(logn)，而不是遍历整个数组。它看起来像这样（省略实际的minHeap实现）：

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

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

请注意，这些是最糟糕的运行时复杂性，我们甚至没有谈到内存考虑因素

如果不了解您的应用程序以及数据是如何形成的，那么很难做出最终的全部建议。如果您只存储1-50和99％的ID，那么您的应用程序只使用1-10，那么可能只需要坚持使用现有的功能。

Answer 2

这是一种更实用的方法，它应该做你需要的。它基本上利用了稀疏数组。

// Find all DOM elements with ids in the container.
const idElements = document.body.querySelectorAll('#container div[id]');

// Get all ids from the DOM elements.
// Note: first have to convert to a real array ([...idElements])
const allIds = [...idElements].map(domElement => parseInt(domElement.id));

// Filter out non-numbers.
const numericIds = allIds.filter(id => Number.isInteger(id));

// Creates a sparse array, e.g. [undefined, true, undefined].
// (The array index of undefined values are available id slots)
const arrayWithGaps = numericIds.reduce((accum, val) => {
  accum[val] = true;
  return accum;
}, []);

// Find the first empty index - this will be the lowest ID available.
const lowestAvailableId = arrayWithGaps.findIndex(val => typeof val === 'undefined');

console.log(lowestAvailableId);

<div id="container">
  <div id="0"></div>
  <div id="1"></div>
  <div id="3"></div>
  <div id="4"></div>
  <div id="5"></div>
  <div id="16"></div>
  <div id="22"></div>
</div>

编辑：如果reduce有点外国或不太可读，你可以使用forEach。实际上，也许它在这里更有意义：

const arrayWithGaps = [];
numericIds.forEach(id => arrayWithGaps[id] = true);

Answer 3

您可以执行以下操作：

let el = document.querySelectorAll('div:not(#container)');
let elArray = [...el].map(i=>i.getAttribute('id'));
var arrayLength = Math.max.apply(Math, elArray);
var missing = [];

for ( var i = 1; i <= arrayLength; i++ ) {
    if ( elArray.indexOf(i.toString()) < 0 ) {
        missing.push(i);
    }
}
missing = missing.map(item => parseInt(item));
var min = Math.min.apply(Math, missing);
console.log('Lowest possible id is: ', min);

// Create element
var div = document.createElement("DIV");
div.setAttribute('id', min);
var container = document.getElementById('container');
container.appendChild(div);
document.getElementById(min.toString()).innerHTML = min;

<div id="container">
  <div id="1">1</div>
  <div id="3">3</div>
  <div id="4">4</div>
  <div id="5">5</div>
  <div id="16">16</div>
</div>

Answer 4

相当简单的方法，不需要花哨的逻辑

const elems = document.querySelector('#container').children;

const getNextId = (els) => {
  let next = 1;
  if (elems) {// skip this if no existing elements
    const set = new Set([...els].map(({id}) => +id));
    while (set.has(next)) {
      next++;
    }
  }
  return next;
}

console.log('Next id: ', getNextId(elems))

<div id="container">
  <div id="2">2</div>
  <div id="1">1</div>
  <div id="3">3</div>
  <div id="4">4</div>
  <div id="5">5</div>
  <div id="16">16</div>
  <div id="22">22</div>
</div>