蚁人跟蚂蚁军团一起作战，完成过很多了不起的任务。 但是训练蚂蚁军团倒是一个不小的难题，随着军团的壮大，已经有了不到百万只蚂蚁服役；为了便于管理，蚁人先让他们排成一个 � × � ( 1 ≤ � , � ≤ 1 0 6 , � × � ≤ 1 0 6 ) n×m(1≤n,m≤10 6 ,n×m≤10 6 ) 方阵。 其中每个蚂蚁都有自己的武力值 � ( 1 ≤ � ≤ 1000 ) x(1≤x≤1000)，那么问题来了，每一列有多少只蚂蚁的武力值跟这一列最后一个蚂蚁的武力值相等。（注意：统计的数据包含这一列的最后一只蚂蚁） 如果能回答出来蚁人可以带你去体验一次量子领域（如果你不害怕回不来的话）。 输入格式 第一行包含两个正整数 � , � n,m； 接下来 � n 行每行包含 � m 个整数表示这一行每个蚂蚁的武力值。 输出格式 输出包含 � m 个空格隔开的整数表示每一列多少只蚂蚁的武力值跟这一列最后一个蚂蚁的武力值相等。c++

以下是 C++ 代码实现：

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 1e6 + 10;

int n, m;
int a[N];
unordered_map<int, int> cnt;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> a[(i - 1) * m + j];

    for (int j = 1; j <= m; j ++ )
    {
        cnt.clear();
        for (int i = 1; i < n; i ++ )
            cnt[a[(i - 1) * m + j]] ++ ;
        cout << cnt[a[(n - 1) * m + j]] + 1 << ' ';
    }

    return 0;
}

思路解析：

我们可以利用哈希表 unordered_map 来统计每一列中每个武力值出现的次数。具体实现时，我们对于每一列，取出该列的最后一个蚂蚁的武力值 x，然后遍历该列中除了最后一个蚂蚁外的所有蚂蚁，将它们的武力值存入哈希表中。遍历完该列中的所有蚂蚁后，我们只需要在哈希表中查询 x 对应的出现次数即可得到答案。

时间复杂度分析：

对于每一列，我们需要遍历其中的 n - 1 只蚂蚁，将它们的武力值插入哈希表中，时间复杂度为 O(n)。总共有 m 列，所以总时间复杂度为 O(mn)。

注意事项：

由于每一列的哈希表都是独立的，所以为了节省空间，我们可以在每次对某一列进行统计时，先将哈希表清空，然后再重新统计。