JavaScript 确保所有数字都是唯一的，如果不是加一(或更多)

Question

我正在尝试在 d3 图表上放置一些标签。

我有一个 DATA 对象，每个对象都有一个 DATA.rowOffset 值。基本上我的代码计算 DATA.rowOffset 并像这样设置它:d.rowOffset = Math.floor(d.total/heightSquares); 但有时 rowOffset 是相同的，因此标签呈现在彼此之上。

我需要循环遍历此 DATA 并检查重复项，然后只对任何重复项 +1。

我尝试了一种方法，它查看了之前的 .rowOffset，然后将 1 添加到当前的 rowOffset，但是如果重复项超过 2 个，那将不起作用.

我确信有更简单的方法......也许。

编辑:这是我主要尝试的一些代码 if (d.rowOffset === DATA[i-1].rowOffset) d.rowOffset++; 所以它会检查前一行的偏移量。我想我需要循环遍历所有数据，然后在发现重复数据时重新开始循环。

DATA.forEach(function(d, i) {
      d.amt = +d.amt;

      d.units = Math.floor(d.amt / squareValue);

      sumTotal = sumTotal + d.units;
      d.total = sumTotal;



      d.rowOffset = Math.floor(d.total / heightSquares);

      if (i > 0) {
        console.log(DATA[i - 1].rowOffset);
        if (d.rowOffset === DATA[i - 1].rowOffset) d.rowOffset++;
      }

Answer 1

这是您可以采用的一种方法。

你初始化了一个空的 Set数据结构来跟踪您到目前为止遇到的唯一值。您遍历数组并为每个值执行以下操作:

• 如果以前遇到过该值，则递增它直到它不匹配任何以前遇到的值
• 更新遇到的值以包含这个新值
• 用新值替换旧值

代码如下:

function incrementDups(arr) {
  // a set of encountered unique values
  const encounters = new Set();

  // increment each duplicate until it has no duplicates
  return arr.map(num => {
    while (encounters.has(num)) {
      num += 1;
    }
    encounters.add(num);
    return num;
  });
}

console.log(
  incrementDups(
    [1, 2, 2, 3, 2, 2, 4] // [1, 2, 3, 4, 5, 6, 7]
  )
);

console.log(
  incrementDups(
    [1, 1, 1, 1, 1, 1, 1] // [1, 2, 3, 4, 5, 6, 7]
  )
);

console.log(
  incrementDups(
    [1, 99, 55, 4, 55, 2] // [1, 99, 55, 4, 56, 2]
  )
);

上面的解决方案具有二次最坏情况时间复杂度。产生这种情况的输入是一个只包含重复项的数组，例如 [1, 1, 1, 1]，其中嵌套的 while 循环的最后一次迭代将运行N 递增。尽管如此，平均而言，该算法的性能应该相当不错。

可以通过使用更多空间来记住某个重复项的最后增量值并将其用作增量的起始值而不是数字本身来进一步优化。

现在，上面的代码实际上做了相当多的重复。如果我们有 [2, 2, 2, ...]，对于每个 2，我们将从 2 开始递增， 3、4 等，尽管从技术上讲，之前的 2 已经为我们完成了工作。理想情况下，我们希望第一个 2 从 2 开始计数，第二个 2 从 3 开始计数，等。这对于连续值的大型数组特别有用。例如，如果我们有 [1, 2, ... 99, ... 2, 2, 2, 2/* 100 次 */]，使用第一种算法，每个 2 将从 2 计数到 99 加上下一个唯一值的递增次数。另一方面，使用这种新方法只有第一个 2 可以做到这一点。下一个 2 只会增加 99 到 100，下一个 100 到 101 等等。如果我们像以前一样得到一个只有重复项的数组，[1, 1, 1 ...]，每个 1 现在只需要递增一次而不是去通过整个范围。

这将时间复杂度收紧到 O(N*max(array))，它仍然是二次的，但仅取决于值的范围，而不是像以前那样重复的数量。它也针对您的特定情况进行了更优化，因为您会期望一组值彼此接近的低数字。

要跟踪此信息，我们可以使用 Map一个数字到它递增到的最新唯一值。

function incrementDups(arr) {
  // a set of encountered unique values
  const encounters = new Set();

  // a map of the last unique non-duplicate for each value
  const lastNonDup = new Map();

  // increment each duplicate until it has no duplicates
  return arr.map(num => {
    let updatedNum = lastNonDup.has(num) ? lastNonDup.get(num) : num;
    while (encounters.has(updatedNum)) {
      updatedNum += 1;
    }
    encounters.add(updatedNum);
    lastNonDup.set(num, updatedNum);
    return updatedNum;
  });
}

console.log(
  incrementDups(
    [1, 2, 2, 3, 2, 2, 4] // [1, 2, 3, 4, 5, 6, 7]
  )
);

console.log(
  incrementDups(
    [1, 1, 1, 1, 1, 1, 1] // [1, 2, 3, 4, 5, 6, 7]
  )
);

console.log(
  incrementDups(
    [1, 99, 55, 4, 55, 2] // [1, 99, 55, 4, 56, 2]
  )
);