c - 获取子矩阵中不同元素的数量

比赛结束了。
问题陈述：
输入：n阶方阵和表示子矩阵的查询。
(x1, y1, x2, y2)
x1, y1表示子矩阵的左上角，x2, y2表示子矩阵的右下角。
输出：此子矩阵中不同元素的数目。
限制条件：
时限=1秒
1≤n≤300
1≤Q≤10^5
1≤ai，j≤10
1≤X1≤X2≤N
1≤Y1≤Y2≤N
这就是我尝试过的：

#include<stdio.h>
//#include<conio.h>
int main()
{
  //clrscr();
  int a[300][300], test[100000], count[10], m, n, c, j, p, q, r, s;
  long qu, re, i;

  scanf("%d", &n);

  for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
      scanf("%d", &a[i][j]);
    }
  }

  scanf("%ld", &qu);
  for (re = 0; re < qu; re++)
  {
    c = 0;
    for(i = 0; i < 10; i++)
    {
      count[i] = 0;
    }

    scanf("%d %d %d %d", &p, &q, &r, &s);
    for (i = (p-1); i < r; i++)
    {
      for (j = (q-1); j < s; j++)
      {
        m = a[i][j];
        count[--m]++;
      }
    }

    for (i = 0; i < 10; i++)
    {
      if (count[i] != 0)
      {
        c++;
      }
    }
    test[re] = c;
  }

  for(i = 0; i < qu; i++)
  {
    printf("%d\n", test[i]);
  }

  //getch();
  return 0;
}

但是我有一个时间限制错误。
它必须用每个数字的累积频率来做一些事情。
有人能为这个问题提出一个有效的算法吗？

最佳答案

初始化并跟踪哈希映射。
遍历子矩阵的条目，对于每个条目，
检查它是否已经在散列映射中；
否则，将total_distinct_entries增加1，并将此项添加到哈希映射。
见http://en.wikipedia.org/wiki/Hash_table。
编辑：另请参见http://en.wikipedia.org/wiki/Set_data_structure，特别是关于实现的部分。在C++中，标准库中有一个std::set数据结构。

关于c - 获取子矩阵中不同元素的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20727021/