@vikas ur algo will search for 1st element of 1d in whole 2d array, on worst case u'll search it in n^2, then search for all 1d elements in 2d in O(n) so whole complexity goes to O(n^2 +n) it can be reduced if we use hashing of 1d array, and count_found and while searching for 1st element of 1d in 2d array, if it's found make temp[i][j] as true(even though its not first element) and false if its not in 1d hash, and increase count_found this will reduce to O(n^2)
surender On 11/1/11, vikas <[email protected]> wrote: > ok, > so do it like this; > 1. create boolean array > boolean temp[][] = new boolean[row][column]; > init(temp, true); > > 2. traverse the array for the 1d array of 0th index and then a > recursive search > if search fails, or position already contains false, return and search > again > > boolean search(int searchArray[][], int givenArray[], int rpos, int > cpos, int gpos){ > if(gpos > givenArray.len) return false; > if(temp[rpos][cpos] == false) return false; > if(searchArray[rpos][cpos] == givenArray[gpos]) > { > temp[rpos][cpos] = search(searchArray, givenArray, rpos > +1, cpos, gpos+1)| > search(searchArray, > givenArray, rpos-1, cpos, gpos+1) | > search(searchArray, > givenArray, rpos, cpos+1, gpos+1)| > search(searchArray, > givenArray, rpos+1, cpos-1, gpos+1) > } > if(temp[rpos][cpos]) return true; > if(cpos < searchArray.len) > search(searchArray, givenArray, rpos, cpos+1, 0); > else > search(searchArray, givenArray, rpos+1, 0, 0); > > } > > On Nov 1, 4:25 pm, SAMM <[email protected]> wrote: >> For example :- >> >> 2d array :: >> >> 1 2 3 4 5 6 >> 7 8 9 10 11 12 >> 13 14 15 16 17 18 >> 19 20 21 22 23 24 >> >> we hav 1d array as :-- 13 2 21 10 23 12 >> >> So the 1d array is a subset of 2d array ... >> >> On 11/1/11, vikas <[email protected]> wrote: >> >> >> >> > what do you mean by subset of 1D present in the 2D array? is it >> > something like 3245 , the search may be 3245/ 24/ 45/ .... all 16 >> > subsets need to be searched? >> >> > On Oct 28, 12:02 pm, SAMMM <[email protected]> wrote: >> >> How do u plan to implement it ??? >> >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit this group at >> >http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> Somnath Singh > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
