[algogeeks] Re: majority element

[J.Guo]

**Presume the majority exists**, the following algo use O(1) space and
only scan the array one pass.

It is simple idea of counting. If there exists a majority elements in
the array, it must be the remaining element on the counter after we
consider all elements.

int getMajority(int A[], int n){

int count=0;
int val=0;
for (int i=1;in;i++){
if(count==0)
{
val=A[i];
count++;
}
else if (val==A[i])
count++;
else// val != A[i]
count--; 
}

return val;

}


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Finding median in theta(n^lg3) time

[J.Guo]

1)Take a look at Quick Sort, especially how the partition works.
2)Try to write an algo to select the kth smallest element in an
unsorted array.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---