3

这是我的面试问题，我有点难过。给定一个由 k 个元素组成的数组，设计一个线性时间算法来确定列表是否具有多数元素，其中多数元素是在列表中出现超过 k/2 次的元素。

4

4 回答 4

5

您可以使用及时运行的Boyer 算法O(n)。它通过数组两次。

该算法对多数元素使用初始candidate值，以及count初始设置为零的计数器。

第一遍看起来像这样：

int count = 0;
T candidate = null;
foreach (var element in array) {
    if (count == 0) {
        candidate = element;
        count = 1;
    } else {
        if (candidate == element) {
            count++;
        } else {
            count--;
        }
    }
}

如果存在多数元素，candidate则在循环结束时将等于它。但是，如果没有多数元素，则候选可能包含误报。第二遍处理该问题：

count = 0;
foreach (var element in array) {
    if (element == candidate) {
        count++;
    }
}
if (count > array.Length/2) {
    Console.WriteLine("Majority element is {0}", candidate);
} else {
    Console.WriteLine("No majority element");
}
于 2013-11-05T20:31:37.253 回答
2

您可以将数组的元素散列为整数值，其中元素的值是散列的键，散列的值是数组中每个元素出现次数的计数。您还可以将最大出现次数存储为最大值；如果 max > k/2，则列表具有多数元素，您甚至不需要再次遍历哈希。

于 2013-11-05T20:22:58.593 回答
1

Robert S Boyer and J Strother Moore wrote an algorithm that finds the majority in O(n) time and O(1) space, and can be used on-line, for instance with data stored on magnetic tape (assuming a single rewind). The idea is to keep at all times a candidate winner, incrementing a count by 1 each time the candidate is seen, decrementing the count by 1 each time some other candidate is seen, and resetting the candidate with the current item whenever the count is zero. The surviving candidate is in the majority, if a majority exists; that requires a separate pass through the data, counting the number of appearances of the candidate. Boyer and Moore (the same guys that wrote the string-matching algorithm) wrote a delightful paper它不仅描述了算法，还描述了他们的 FORTRAN 77 程序的正式证明。我在我的博客中有一个 Scheme 的实现。

于 2013-11-05T20:34:56.133 回答
0 
Create Hashmap, with elements as keys and counters as values
For each item
   If the item doesn't have an entry in the hashmap,
       Create a counter, starting with a zero value

   Increment the counter stored in the hashmap
   If the count > k /2
       Then this element is the majority element; return true

There is no max if we reach this line; return false
于 2013-11-05T20:30:28.130 回答