c++ - 在 C++ 中对二维数组进行排序

Question

假设我有一个像这样的二维数组 a[4][2]:

1 4
2 3
3 2
4 1

我想按照第二个数字的递增顺序对这个数组中的数组进行排序，即在排序之后，我希望数组是这样的:

4 1
3 2
2 3
1 4

我想制作一个存储第二列中数字索引的映射，然后制作第二列中数字的数组并对该数组进行排序，然后根据第二列的新顺序重建数组和 map 。然而，问题在于第二列中的两个数字可能不同，因此如果数字 i 出现两次，map[i] 将只存储其最后一个索引。此外，手动检查第一个数字对应于第二个数字的位置将花费 O(n^2) 时间。我想在 O(n log n) 中完成。有没有人有什么建议？是否有任何内置方法(C++ 4.3.2/4.8.1)？

提前致谢。

Answer 1

您可以使用 std::sort 轻松完成此操作.您需要提供自定义比较器，但这不是问题。

如果你使用 std::array 就容易多了定义您的二维数组，如下所示:

std::array< std::array< int, 2 >, 4 > twoDArray;

然后您可以按如下方式对其进行排序:

std::sort( twoDArray.begin(), twoDArray.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
{
    return a[1] < b[1];
}

对 C 风格的数组做同样的事情仍然是可能的，但是需要一个自定义迭代器的实现，它一次推进整个“行”，因为标准迭代器(即指针)会将 2D 数组视为它是一维的。

这是一个使用 C++ 数组的完整示例:

std::array< std::array< int, 2 >, 4 > arr   = {{ { 1, 4 },
                                                 { 2, 3 },
                                                 { 3, 2 },
                                                 { 4, 1 } }};

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[0] < b[0];
    } );

std::sort( arr.begin(), arr.end(), []( const std::array< int, 2 >& a, const std::array< int, 2 >& b )
    {
        return a[1] < b[1];
    } );