example : let the array be { a,b,a,b,c,d,e,d,d,e,f};
now...
step 1 :pick any 2 different element and remove from the array till
array contains only same elements or any single element .......// dis
is implemented wid the above mentioned funtion " build() "
if there is any element whose occurence is greater than n/2 than u ll
always get an unique value left after step 1 , it wont depend on the
way u select 2 different element n removing them.
On Apr 15, 12:43 am, vishwakarma <[email protected]> wrote:
> Let A be the input array;
>
> Now algorithm is follows;
>
> struct leave{
> int cand;
> int count;};
>
> struct leave tree[1200000];
>
> void build(int s,int e,int node ,int *A)
> {
> if(s == e){
> tree[node].cand = A[s];
> tree[node].count = 1;
> return;
> }
> else{
> int mid = (s+e)>>1;
> build(s,mid,2*node,A);
> build(mid+1,e,2*node+1,A);
>
> if(tree[2*node].cand == tree[2*node+1].cand){
> tree[node].cand = tree[2*node].cand;
> tree[node].count = tree[2*node].count +
> tree[2*node+1].count;
> }
> else{
> if(tree[2*node].count > tree[2*node+1].count){
> tree[node].cand = tree[2*node].cand;
> tree[node].count = tree[2*node].count -
> tree[2*node+1].count;
> }
> else{
> tree[node].cand = tree[2*node+1].cand;
> tree[node].count = tree[2*node+1].count -
> tree[2*node].count;
> }
> }
> }
>
> }
>
> int main()
> {
> //read Array A
> build(1,n,1);
>
> //sort array A
>
> int val = Tree[1].cand;
>
> //perform binary search on sorted array A
> //if its count is strictly greater than n/2 then yes else no
> On Apr 15, 12:28 am, LALIT SHARMA <[email protected]> wrote:
>
> > Yes , I also need the same...Thanks for the help .
>
> > On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
> > <[email protected]>wrote:
>
> > > I can post solution of this complexity if you want !!
>
> > > On Apr 15, 12:19 am, vishwakarma <[email protected]> wrote:
> > > > complexity : O(n) + O(nlogn)
>
> > > > Sweety wrote:
> > > > > Question :Let A[1..n] be an array of integers. Design an efficient
> > > > > divide and conquer algorithm to determine if A contains a majority
> > > > > element, i.e an element appears more than n/2 times in A. What is the
> > > > > time complexity of your algorithm?
>
> > > > > Answer:
> > > > > a[1..n] is an array
> > > > > int majorityElement(int a[], int first, int last)
> > > > > {
> > > > > If (first = = last)
> > > > > {
> > > > > return a[first]; // Array has one element and its count =
> > > > > 1
> > > > > and it is major element
> > > > > }
> > > > > mid= (first+last)/2;
>
> > > > > (majorL,countL)= majorityElement(a,first,mid);
> > > > > (majorR,countR)= majorityElement(a,mid
> > > > > +1,last);
> > > > > n = total elements in an array;
> > > > > If(majorL==majorR)
> > > > > return(countL+countR);
> > > > > else
> > > > > {
> > > > > If(countL>countR)
> > > > > return(majorL,countL);
> > > > > elseif(countL< countR)
> > > > > return(majorR,countR);
> > > > > else
> > > > > return(majorL,majorR);
> > > > > }
> > > > > if(countL>n/2)
> > > > > temp1=majorL;
> > > > > if(countR>n/2)
> > > > > temp2=majorR;
>
> > > > > If(temp1 = = temp2)
> > > > > return temp1;
> > > > > elseif(countL>countR)
> > > > > return temp1;
> > > > > else (countR>countL)
> > > > > return temp2;
> > > > > else
> > > > > return -1;
> > > > > }
>
> > > > > int main()
> > > > > {
> > > > > int a[8] = {2,3,2,2,4,2,2,2};
> > > > > int first =1;
> > > > > int last=8; //change the value of last when the array
> > > > > increases or decreases in size
> > > > > int x = majorityElement(a,first,last);
> > > > > if(x= = -1)
> > > > > printf(“No Majority Element”)
> > > > > else
> > > > > Majority element = x;
> > > > > }
>
> > > --
> > > You received this message because you are subscribed to the Google
> > > Groups> > "Algorithm Geeks" group.> To post to this group, send
> > > [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.
>
> > --
> > Lalit Kishore Sharma,
>
> > IIIT Allahabad (Amethi Capmus),
> > 6th Sem.
--
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.
