大小为n的数组，其中一个元素n/2次

Question

给定一个n个整数的数组，其中一个元素出现超过n/2次。我们需要在线性时间和恒定的额外空间中找到该元素。 YAAQ：又一个数组问题。

Answer 1

我有一个偷渡怀疑它是沿着线的东西（在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; 
} 

这听起来不大可能奏效，但它确实。 （Proof as a postscript file，由Boyer/Moore提供）

Answer 2

我首先想到的（不充分）将是：

• 排序到位阵列
• 返回中间元素

但是，这将是为O（n log n）的，就像任何递归解决方案一样。

如果你可以破坏性地修改数组（以及其他各种适用的条件），你可以用它们的计数或其他方法来进行通过替换元素。你知道关于阵列的其他事情吗？你可以修改它吗？

编辑留下我的答案在这里为子孙后代，但我认为Skeet明白了。

Answer 3

如何： 随机选择K个元素的一个小子集并查找重复项（例如前4个，前8个等）。如果K == 4，那么没有得到至少2个副本的概率是1/8。如果K == 8，那么它会下降到1％以下。如果你发现没有重复，直到你重复这个过程。 （假设其他元素是随机分布的，那么这个性能会非常差，例如49％的阵列=“A”，51％的阵列=“B”）。

例如为：

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  

这是一个恒定的顺序操作（如果所述数据集是不坏），以便然后执行所述阵列的线性扫描，以便（N）来验证。

Answer 4

那么你可以做一个就地基数排序here[pdf]这不需要额外的空间和线性时间。那么您可以对连续的元素进行一次统计并终止于> n/2的计数。

Answer 5

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; 
    } 
} 

我不是这段代码的作者，但是这可以解决你的问题。第一部分寻找潜在的领导者，第二部分检查它是否在阵列中出现超过n/2次。

Answer 6

找到中位数，它在未排序的数组上需要O（n）。由于多于n/2个元素等于相同的值，因此中位数也等于该值。

Answer 7

这是我最初想到的。

我试图保持不变的“一个元素出现超过n/2次”，同时减少了问题集。

让我们开始比较[i]，a [i + 1]。如果它们相等，我们比较[i + i]，a [i + 2]。如果不是，我们从数组中删除[i]，[i + 1]。我们重复这个直到i> =（当前大小）/ 2。此时我们将有'THE'元素占据第一个（当前大小）/ 2个位置。 这将保持不变。

唯一需要注意的是，我们假设该阵列是一个链表[它给一个O（n）的复杂性。]

说什么人？

-bhupi

在PHP

Answer 8

---请检查它是否是正确的

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; 
} 

Answer 9

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);