Okay, i thought it this way: iterate through the whole matrix, and take the value as a "key" to a hash table. and the value corresponding to the key would be the "count". increment the count everytime you encounter the same key. it is very easy to implement this in python (using dictionary) but i am not sure what will be the most efficient data structure to implement this in c/c++.
Vishal On Mon, May 30, 2011 at 10:31 AM, ross <jagadish1...@gmail.com> wrote: > @vishal > Hi, > I do not get you. > Can you please elaborate a little more how you ll use hash? > > On May 30, 8:50 am, Vishal Thanki <vishaltha...@gmail.com> wrote: >> what about using a hash function? >> >> >> >> >> >> >> >> On Mon, May 30, 2011 at 10:18 AM, ross <jagadish1...@gmail.com> wrote: >> > Given a matrix, you need to find the number of blocks in it. >> > A block has the same numbers. >> > EG: >> > 1 1 3 >> > 1 2 3 >> > 2 2 4 >> > has 4 blocks namely, >> > 1 1 >> > 1 >> > 2 >> > 2 2 >> >> > 3 >> > 3 >> >> > 4 >> >> > 1 2 3 >> > 4 5 6 >> > 7 8 9 >> > has 9 blocks >> >> > 1 1 1 >> > 1 1 3 >> > 4 4 5 >> > has 4 blocks, >> > 1 1 1 >> > 1 1 >> >> > 3 >> >> > 5 >> >> > 4 4 >> >> > I used an algorithm as follows, >> > for each element[i,j] in the matrix, >> > enqueue adjacent indices into a queue if they contain the same >> > element. >> > else >> > incremt blockcount; >> >> > return blockcount; >> >> > But, this complexity is O(n^3) any better solution exists? >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group >> > athttp://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
