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

Question

这是 a problem from the December 2013 CodeChef Challenge比赛已经结束。

问题陈述:

Input: Square matrix of order n and a query which will denote the submatrix.

(x1, y1, x2, y2)

x1, y1 denotes the upper left and x2, y2 denotes the lower right end of submatrix.

Output: Number of distinct elements in this submatrix.

Constraints:

• Time limit = 1 sec
• 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;
}

但是我遇到了一个 TLE(超出时间限制)错误。

它必须对每个数字的累积频率做一些事情。

有人可以针对这个问题提出一个有效的算法吗？

Answer 1

初始化并跟踪 HashMap 。

遍历子矩阵的条目，对于每个条目，

• 检查它是否已经在 HashMap 中；
• 如果不是，则将 total_distinct_entries 加 1，并将此条目添加到 HashMap 中。

参见 http://en.wikipedia.org/wiki/Hash_table .

编辑:另见 http://en.wikipedia.org/wiki/Set_data_structure ，特别是关于实现的部分。在 C++ 中，标准库中提供了一个 std::set 数据结构。