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 times */]，使用第一種算法，則每個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] 
 
) 
 
);