随机播放，然后查找并替换二维数组中的重复项 - 无需排序

Question

我正在为这个棘手的事情寻找有效的算法（或任何算法..）。我会简化我的问题。在我的应用程序中，这个数组大约大 10000 倍:)

我有一个这样的二维数组：

是的，每一行都有从 0 到 4 的值，但顺序不同。顺序很重要！我不能简单地对其进行排序和解决:)
然后，我通过选择随机索引并交换它们来洗牌 - 几次。结果示例：

我在行中看到重复项，这不好。算法应该找到这些重复项并将它们替换为不会成为特定行中另一个重复项的值，例如：

能分享一下你的想法吗？也许这个问题已经有非常著名的算法了？我将不胜感激任何提示。

编辑 T_G 的说明：随机播放后，特定行无法与其他行交换值。它需要找到重复项并将其替换为剩余的可用（任何）值 - 这不是另一个重复项。

洗牌后：

步骤：我有0；我没有看到另一个零。接下来。

我有1；我看到另一个 1；我应该改变它（第二个）；此行中没有 2，因此让我们将此重复项 1 更改为 2。

我有1个；我看到另一个 1。我应该改变它（第二个）；此行中没有 3，因此让我们将此重复项 1 更改为 3。等...

因此，如果您输入此行：

0 0 0 0 0 0 0 0 0

你应该得到：

0 1 2 3 4 5 6 7 8

Answer 1

尝试这样的事情：

// Iterate matrix lines, line by line
for(uint32_t line_no = 0; line_no < max_line_num; line_no++) {

  // counters for each symbol 0-4; index is symbol, val is counter
  uint8_t counters[6];

  // Clear counters before usage
  memset(0, counters, sizeof(counters));

  // Compute counters
  for(int i = 0; i < 6; i++)
    counters[matrix[line_no][i]]++;

  // Index of maybe unused symbol; by default is 4
  int j = 4; 

  // Iterate line in reversed order
  for(int i = 4; i >= 0; i--) 
    if(counters[matrix[line_no][i]] > 1) { // found dup
      while(counters[j] != 0) // find unused symbol "j"
        j--;
      counters[matrix[line_no][i]]--; // Decrease dup counter
      matrix[line_no][i] = j; // substitute dup to symbol j
      counters[j]++; // this symbol j is used
    } // for + if
} // for lines

随机播放，然后查找并替换二维数组中的重复项 - 无需排序

Shuffle, then find and replace duplicates in two dimensional array - without sorting

c

arrays

algorithm

replace

duplicates