2013-12-08 130 views
0

我已經想好了下面的,但它需要大量的內存。元素在給定範圍內的子矩陣中唯一元素的數量?

由於我需要在任何子矩陣中找到唯一元素,並且元素在1-10範圍內,我爲每個矩陣成員創建了一個大小爲10的數組,其中存儲了每個元素到該矩陣的出現次數成員(從左邊)在那一行。

例如

如果行是1, 2, 2, 4, 3, 5

然後arr[3][10]={1,2,0,1,0,0,0,0,0,0} //for the 3rd element '4', '1' occurred once, '2' twice and '4' once.

arr[5][10]={1,2,1,1,1,0,0,0,0,0} //for the last element '5'

因此,我可以通過只經過每個所述兩個陣列的找出任意兩個成員之間的唯一元件的數量,並查看哪些的陣列成員是不同的。

我可以推子矩陣中的每一行中的所有獨特元素爲set並找到獨特的元素的數量。

然而,這種方法需要大量的存儲器,如果矩陣的大小增加。有沒有更好的方法來做到這一點?

回答

0

你的做法是正確的。繼續,你會得到AC。我實現了你在問題中寫下的內容,並獲得了AC。使用尺寸爲[300] [300] [10]的三維矩陣,並按照您的建議進行。內存要求不會太高。