Hi Bittu,
Your algorithm uses Linear extra space. which is proportional to the
input used.
There is a better algorithm which is linear in time and does alot
better .
int Majoritycount(int [] A) {
int ctr=1;
//counter is a variable to indicate the relative importance of the
element. as successive matches are encountered
increment counter. if a mismatch occurs decrement counter.
int candidate = A[0];
//ASSIGN FIRST ELEMENT AS A POTENTIAL CANDIDATE FOR MAJORITY
int mindex=0;
//holds the index of the maximum element
N= a.length( );
for(i = 0 to N){
if(a[i]==a[mindex]) ctr++; //match - incr counter
else ctr--; //mismatch - dec counter
if(ctr==0) {
//this implies that the element at mindex has lost the credibility to
become the majority element
ctr=1;
mindex=i;
candidate=A[i];
}
return candidate;
}
}
On Sep 10, 7:23 pm, Dave <[email protected]> wrote:
> One problem in your algorithm is that the additional array has to be
> large enough to handle all of the values in the array, so, e.g.,
> multiply all of your values by a million and you will see that the
> work goes up by a factor of a million.
>
> It can be done without the additional array, and therefore in a way
> that is independent of the specific values in the array.
> Seehttp://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html.
>
> Dave
>
> On Sep 10, 7:06 am, bittu <[email protected]> wrote:
>
> > i think my concept is right
>
> > lets us take array a[1..n];={1,1,1,2,1,3};
> > n=6;
> > n/2+1=4;
>
> > so take another array aux[];
>
> > which is very helpful to findout hw much time each elemnt arrive in a
> > so its count teh no. of time..
>
> > fro i=0 to n
> > aux[a[i]]++;
>
> > so aux now contains aux[]={0,4,1,1,0,0};
>
> > and just simply find the maximum which gives the 4 and it is clear 1
> > comes 4 times and which >n/2+1 ans is majority element
>
> > right me if i m wrong ....
>
> > Regards
> > Shashank "Don't b evil U can Earn while u learn"
> > 09166674831
--
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.
