the implementation of the hashmap in prev soln(to achieve constant time) is non-trivial and is based on some exercise of Cormen.
better and simple: Think of these points as nodes of the graph use the UnionFind(quickunion) data structure... and everytime a union is done add 1 to the component united. find the one with count>500 -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf <[email protected]>wrote: > I agree.... But that worst case will never come here. There are > between 2 and 500 keys. And all keys are different.... So how would > the worst case come?? > > On 4/14/10, gaurav kishan <[email protected]> wrote: > > This will be done in one pass i.e O(n). > > On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan > > <[email protected]>wrote: > > > >> Can everyone check this out and let me the issues ? > >> > >> int[] i=new > >> int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56}; > >> int count=1,element=i[0]; > >> for(int j=1;j<i.length;j++) > >> { > >> if(element==i[j]) > >> count++; > >> else > >> { > >> count--; > >> if(count==0) > >> { > >> element=i[j]; > >> count=1; > >> } > >> } > >> > >> } > >> System.out.println("Mode is "+element); > >> } > >> > >> Regards, > >> Gaurav Kishan > >> > >> On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar > >> <[email protected]>wrote: > >> > >>> ya over here its >501 rite????? > >>> > >>> > >>> On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain <[email protected]> > wrote: > >>> > >>>> If m thinking right, > >>>> That works if mode occurs >=n/2 times in the array > >>>> > >>>> Best, > >>>> Prakhar Jain > >>>> http://web.iiit.ac.in/~prakharjain/ > >>>> > >>>> > >>>> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar < > [email protected] > >>>> > wrote: > >>>> > >>>>> can we make use of majority VOTE ALGORITHM? > >>>>> > >>>>> > >>>>> On Wed, Apr 14, 2010 at 4:14 PM, Gauri <[email protected]> wrote: > >>>>> > >>>>>> Say If I have an array of 1,000 32-bit integers .And one of the > value > >>>>>> is occuring 501 number of times or more in the array. Can someone > help > >>>>>> me devise an efficient algorithm for the same ? > >>>>>> > >>>>>> Thanks & Regards > >>>>>> Gauri > >>>>>> > >>>>>> -- > >>>>>> 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]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > . > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > Sent from my mobile device > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > -- 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.
