獲取子矩陣中不同元素的數量

Question

這是a problem from the December 2013 CodeChef Challenge並且比賽已結束。

問題陳述：

輸入： n階方矩陣，其將表示所述子矩陣的查詢。

(x1, y1, x2, y2)

x1, y1表示左上和x2, y2表示子矩陣的右下端。

輸出：該子矩陣中不同元素的數量。

限制條件：

• 時限= 1秒
• 1≤N≤300
• 1≤Q≤10^5
• 1≤艾，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

初始化並跟蹤哈希映射。

迭代通過子矩陣的項，並且對於每個條目，

• 檢查，如果它是在哈希映射已經;
• 如果不是，則將total_distinct_entries加1，並將該條目添加到散列映射中。

參見http://en.wikipedia.org/wiki/Hash_table。

編輯：另請參閱http://en.wikipedia.org/wiki/Set_data_structure，特別是實施部分。在C++中，標準庫中提供了一個std::set數據結構。

Answer 2

EDITED

（含1個工作基於索引）

首先嚐試：

不要蠻力，存儲在計數陣列中的每個數字的計數作爲問題的海報給了，但是這絕對會超出很多測試用例。

第二： 由於我們知道條目只能達到10我們可以嘗試存儲每個數字出現在子矩陣（1,1）到（i，j）的次數。 假設這個矩陣是Q. Q [i] [j] [k]給出k次出現在i，j子矩陣中的次數。

for i from 1 to n 
    for j from 1 to n 
     for k from 0 to 10 
      Q[i][j][k] = Q[i-1][j][k] + Q[i][j-1][k] - Q[i-1][j-1][k] 
     Q[i][j][A[i][j]]++ 

這可以爲O（n^2 *（k））的時間來完成：

這可以有效地如下計算。由於k小於10，效率很高。

現在回答這個疑問是很容易的：

對於查詢（X1，Y1） - （x2，y2）

int count[10] 
for k from 0 to 10 
    // x is row and y is column 
    count[k] = Q[x2][y2][k] - Q[x1-1][y2][k] - Q[x2][y1-1][k] + Q[x1-1][y1-1][k] 

這回答爲O的所有查詢（k）的時間。由於k從0到10，這是在時間限制內。