需要逻辑方面的帮助 (C)

Question

我需要交换两个非重复序列（数组）中的前 n 个元素，其中 n 是一个随机整数。

序列 1： 1 4 5 6 9 8 2 3 7

序列 2： 3 9 1 2 8 7 4 5 6

如果 n = 4

序列 1： 3 9 1 2 | 9 8 2 3 7

序列2：1 4 5 6 | 8 7 4 5 6

现在我需要通过替换“|”后的重复数字来修复序列。

如何做到这一点？

这是我的努力..

for(left1 = 0; left1<pivot; left1++)
  {
   for(right1 = pivot; right1 < no_jobs; right1++)
    {
     if(S1->sequence[left1] == S1->sequence[right1])
      {
        for(left2 = 0; left2<pivot; left2++)
        {
          for(right2 = pivot; right2<no_jobs; right2++)
          {
            if(S2->sequence[left2] == S2->sequence[right2])
            {
              swap_temp = S1->sequence[right1];
              S1->sequence[right1] = S2->sequence[right2];
              S2->sequence[right2] = swap_temp;
              break;
            }
          } 
        }
      }
    }
  }

Answer 1

使用单个 for 循环交换前 n 个元素非常简单。

for(int i = 0; i < n; i++){
   int tmp = array1[i];
   array1[i] = array2[i];
   array2[i] = tmp;
}

现在您需要找出数组中发生了什么变化。您可以通过比较交换的部件来做到这一点。

int m1 = 0, m2 = 0;
int missing_array1[n];
int missing_array2[n];

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array1[i] == array2[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array2[m2++] = array1[i];
    }
}

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array2[i] == array1[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array1[m1++] = array2[i];
    }
}

Missing_array2 现在包含 array2 中缺少的数字。这些是将在 array1 中重复的所有数字。 Missing_array1 也是如此。接下来，您需要扫描两个数组并用缺失的数字替换重复的数字。

while(m1 >= 0){
    int z = 0;
    while(missing_array1[m1] != array2[n + z]){
        z++;
    }
    array2[n + z] = missing_array2[m1--];
}

while(m2 >= 0){
    int z = 0;
    while(missing_array2[m2] != array1[n + z]){
        z++;
    }
    array1[n + z] = missing_array1[m2--];
}

总之，您可以比较交换的部分以查找每个数组中缺少的值。这些值也是将在相反数组中重复的值。然后扫描每个数组并用其中一个缺失值替换重复值（我假设您不关心哪个缺失值，只要所有值都是唯一的即可。

Answer 2

如果序列的交换部分包含相同的值，则不会有重复 - 执行交换只会打乱前 n 个元素。因此，您需要修复的值是交换序列之一中出现的值。

首先，我将创建 n 个交换元素的直方图，其中序列 1 中的元素计为位 0，序列 2 中的元素计为位 1如果直方图的任何成员非零，则它们仅以一个或另一个顺序出现。

如果有需要修复的值，那么您可以构建一个需要重写的值的查找表。这应该将 i 映射到 i ，除非 i 是直方图中的不对称值之一，在这种情况下它需要映射到另一个不对称值。

Seq1: 1 4 5 6 9 8 2 3 7

Seq2: 3 9 1 2 8 7 4 5 6

如果序列 1 的 n = 4

Seq1: 3 9 1 2 | 9 8 2 3 7

Seq2: 1 4 5 6 | 8 7 4 5 6

直方图

value    1 2 3 4 5 6 7 8 9 
count    3 1 1 2 2 2 0 0 1

映射（当直方图 [S1[i]] & 1 时，将 [S1[i]] 替换为 S2[i] ）

value    1 2 3 4 5 6 7 8 9 
replace  1 6 5 4 5 6 7 8 4

将映射应用于序列 1（i > 1）。 序列 2 的n

Seq1:    3 9 1 2 | 9 8 2 3 7
replace  - - - - | 4 8 6 5 7
result   3 9 1 2 | 4 8 6 5 7

映射（当直方图 [S2[i]] 和 2 时，将 [S2[i]] 替换为 S1[i] ）

value    1  2  3  4  5  6  7  8  9 
replace  1  2  3  9  3  2  7  8  9 

将映射应用于序列 1（当 i > 2 时） n

Seq2:    1 4 5 6 | 8 7 4 5 6
replace  - - - - | 8 7 9 3 2
result   1 4 5 6 | 8 7 9 3 2

或者，用直方图中设置的其他位替换下一个值（迭代替换还需要检查是否用其自身替换值）；我假设只要结果中的值是唯一的，使用什么值作为替换并不重要。