CODEWITHSUNDEEP
algorithm
baskin
baskin

Reputation: 1663

Array of size n, with one element n/2 times

Given an array of n integers, where one element appears more than n/2 times. We need to find that element in linear time and constant extra space.

YAAQ: Yet another arrays question.

Upvotes: 10

Views: 9167

Answers (9)

Mallik
Mallik

Reputation: 1

int n = A.Length;
            int[] L = new int[n + 1];
            L[0] = -1;
            for (int i = 0; i < n; i++)
            {
                L[i + 1] = A[i];
            }
            int count = 0;
            int pos = (n + 1) / 2;
            int candidate = L[pos];
            for (int i = 1; i <= n; i++)
            {
                if (L[i] == candidate && L[pos++] == candidate)
                    return candidate;
            }
            if (count > pos)
                return candidate;
            return (-1);

Upvotes: -2

dbKooper
dbKooper

Reputation: 1045

in php---pls check if it's correct

function arrLeader( $A ){
$len = count($A);
$B = array();
$val=-1;
$counts = array_count_values(array); //return array with elements as keys and occurrences of each element as values
for($i=0;$i<$len;$i++){
    $val = $A[$i];
    if(in_array($val,$B,true)){//to avoid looping again and again
    }else{
     if($counts[$val]>$len/2){
      return $val;
     }
     array_push($B, $val);//to avoid looping again and again
    }
 }
 return -1;
}

Upvotes: -1

baskin
baskin

Reputation: 1663

This is what I thought initially.

I made an attempt to keep the invariant "one element appears more than n/2 times", while reducing the problem set.

Lets start comparing a[i], a[i+1]. If they're equal we compare a[i+i], a[i+2]. If not, we remove both a[i], a[i+1] from the array. We repeat this until i>=(current size)/2. At this point we'll have 'THE' element occupying the first (current size)/2 positions. This would maintain the invariant.

The only caveat is that we assume that the array is in a linked list [for it to give a O(n) complexity.]

What say folks?

-bhupi

Upvotes: 2

rouli
rouli

Reputation:

Find the median, it takes O(n) on an unsorted array. Since more than n/2 elements are equal to the same value, the median is equal to that value as well.

Upvotes: 8

Pyetras
Pyetras

Reputation: 1502

int findLeader(int n, int* x){
    int leader = x[0], c = 1, i;
    for(i=1; i<n; i++){
        if(c == 0){
            leader = x[i];
            c = 1;
        } else {
            if(x[i] == leader) c++;
            else c--;
        }
    }

    if(c == 0) return NULL;
    else {
        c = 0;
        for(i=0; i<n; i++){
            if(x[i] == leader) c++;
        }
        if(c > n/2) return leader;
        else return NULL;
    }
}

I'm not the author of this code, but this will work for your problem. The first part looks for a potential leader, the second checks if it appears more than n/2 times in the array.

Upvotes: 2

MarkusQ
MarkusQ

Reputation: 21950

My first thought (not sufficient) would be to:

  • Sort the array in place
  • Return the middle element

But that would be O(n log n), as would any recursive solution.

If you can destructively modify the array (and various other conditions apply) you could do a pass replacing elements with their counts or something. Do you know anything else about the array, and are you allowed to modify it?

Edit Leaving my answer here for posterity, but I think Skeet's got it.

Upvotes: 0

MahdeTo
MahdeTo

Reputation: 11184

Well you can do an inplace radix sort as described here[pdf] this takes no extra space and linear time. then you can make a single pass counting consecutive elements and terminating at count > n/2.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1502006

I have a sneaking suspicion it's something along the lines of (in C#)

// We don't need an array
public int FindMostFrequentElement(IEnumerable<int> sequence)
{
    // Initial value is irrelevant if sequence is non-empty,
    // but keeps compiler happy.
    int best = 0; 
    int count = 0;

    foreach (int element in sequence)
    {
        if (count == 0)
        {
            best = element;
            count = 1;
        }
        else
        {
            // Vote current choice up or down
            count += (best == element) ? 1 : -1;
        }
    }
    return best;
}

It sounds unlikely to work, but it does. (Proof as a postscript file, courtesy of Boyer/Moore.)

Upvotes: 23

Steve B.
Steve B.

Reputation: 57325

How about: randomly select a small subset of K elements and look for duplicates (e.g. first 4, first 8, etc). If K == 4 then the probability of not getting at least 2 of the duplicates is 1/8. if K==8 then it goes to under 1%. If you find no duplicates repeat the process until you do. (assuming that the other elements are more randomly distributed, this would perform very poorly with, say, 49% of the array = "A", 51% of the array ="B").

e.g.: 

findDuplicateCandidate: 
    select a fixed size subset.
    return the most common element in that subset
    if there is no element with more than 1 occurrence repeat.
    if there is more than 1 element with more than 1 occurrence call findDuplicate and choose the element the 2 calls have in common

This is a constant order operation (if the data set isn't bad) so then do a linear scan of the array in order(N) to verify.

Upvotes: 0

Related Questions