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

Question

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

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

我需要循环执行此操作DATA并检查重复项，然后对任何重复项 +1。

我尝试了一种方法，查看前一个.rowOffset，然后将 1 添加到 current 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 times */]使用第一个算法，每个算法2都会从2到进行计数99，并加上到下一个唯一值的增量。另一方面，使用这种新方法只有第一种方法2可以做到这一点。下一个2只会增加到99，100下一个会100增加到101，依此类推。如果我们像以前一样得到一个仅包含重复项的数组，[1, 1, 1 ...]则每个1现在只需要递增一次，而不是遍历整个范围。

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

为了跟踪此信息，我们可以使用数字到其递增到的最新唯一值的映射。

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