c++ - 根据关系的二维数组对数组进行排序(更高，更低，无关紧要)

Question

我被这个问题困了两天了，还是没搞定。

基本上，我有一个二维数组，其中包含某些数字(在给定范围内)之间的关系:

• 0 = 顺序无关紧要
• 1 = 第一个数字(左栏中的数字)应该是第一个
• 2 = 第二个数字(上排的数字)应该是第一个

所以，我有一些二维数组，例如:

  0 1 2 3 4 5 6
0 0 0 1 0 0 0 2
1 0 0 2 0 0 0 0
2 2 1 0 0 1 0 0
3 0 0 0 0 0 0 0
4 0 0 2 0 0 0 0
5 0 0 0 0 0 0 0
6 1 0 0 0 0 0 0

我的目标是创建一个由给定数字 (0 - 6) 组成的新数组，使其遵循二维数组的规则(例如，0 在 2 之前，但在 6 之后)。我可能还必须检查这样的数组是否存在，然后创建该数组。得到这样的东西:

6 0 2 1 4 5

我的代码

(没关系，但我更喜欢c++)

到目前为止，我尝试从有序数组 0123456 开始，然后根据表格交换元素(但这显然行不通)。我也试过按照表格在另一个数字前面插入数字，但似乎也不起作用。

// My code example
// I have:
//    relArr[n][n]             - array of relations
//    resArr = {1, 2, ... , n} - result array

for (int i = 0; i < n; i++) {
    for (int x = 0; x < n; x++) {
        if (relArr[i][x] == 1) {
          // Finding indexes of first (i) and second (x) number
            int iI = 0;
            int iX = 0;
            while (resArr[iX] != x)
                iX++;
            while (resArr[iI] != i)
                iI++;

          // Placing the (i) before (x) and shifting array
            int tmp, insert = iX+1;
            if (iX < iI) {
                tmp = resArr[iX];
                resArr[iX] = resArr[iI];

                while (insert < iI+1) {
                    int tt = resArr[insert];
                    resArr[insert] = tmp;
                    tmp = tt;
                    insert++;
                }
            }
        } else if (relArr[i][x] == 2) {
            int iI = 0;
            int iX = 0;
            while (resArr[iX] != x)
                iX++;
            while (resArr[iI] != i)
                iI++;

            int tmp, insert = iX-1;
          if (iX > iI) {
                tmp = resArr[iX];
                resArr[iX] = resArr[iI];

                while (insert > iI-1) {
                    int tt = resArr[insert];
                    resArr[insert] = tmp;
                    tmp = tt;
                    insert--;
                }
            }
        }
    }
}

我可能错过了检查是否可以创建数组的正确方法。如果您愿意，请随意使用 vector 。

预先感谢您的帮助。

Answer 1

您似乎在读取输入的同时重新排序输出。我认为您应该将输入解析为一组规则，对规则进行一些处理，然后在最后重新排序输出。

---

问题的约束条件是什么？如果输入说 0 在 1 之前:

  | 0 1
--+----
0 |   1
1 |

它是否也保证它会说 1 在 0 之后？

  | 0 1
--+----
0 |   
1 | 2

如果是这样，您可以忘记 2 并只查看 1 :

  | 0 1 2 3 4 5 6
--+--------------
0 |     1
1 |
2 |   1     1
3 |
4 |
5 |
6 | 1

---

通过读取输入，我将存储一个规则列表。我会为此使用 std::vector<std::pair<int,int>>。它具有 yourPair.first 出现在 yourPair.second 之前的好特性:)

0 before 2
2 before 1
2 before 4
6 before 0

您可以丢弃第二个值永远不是不同规则的第一个值的任何规则。

0 before 2
6 before 0

然后需要对该列表进行排序，以便保证“...在 x 之前”和“x 在...之前”的顺序。

6 before 0
0 before 2

然后将 6 、 0 和 2 移到列表 0123456 的前面，给你 6021345 。

这有帮助吗？