algorithm - 在数组中出现超过 n/3 次的数字

Question

我读过这个问题 Find the most common entry in an array

jon skeet 的回答令人兴奋.. :)

现在我正在尝试解决这个问题，找到一个在数组中出现超过 n/3 次的元素..

我很确定我们不能应用相同的方法，因为可能有 2 个这样的元素会出现超过 n/3 次，并且会产生错误的计数警报......所以我们有什么办法可以调整 jon skeet 的回答为此工作..？

或者是否有任何解决方案可以在线性时间内运行？

Answer 1

Jan Dvorak 的回答可能是最好的：

• 从两个空的候选槽和两个设置为 0 的计数器开始。
• 对于每个项目：
  • 如果它等于任一候选者，则增加相应的计数
  • 否则，如果有一个空插槽（即计数为 0 的插槽），则将其放入该插槽并将计数设置为 1
  • 否则将两个计数器都减 1

最后，对数组进行第二次遍历，以检查候选者是否确实具有所需的计数。您链接到的问题不允许这样做，但我不知道如何避免此修改版本。如果有一个值出现超过 n/3 次，那么它将在一个槽中，但你不知道它是哪一个。

如果这个问题的修改版本保证有两个值超过n/3元素（通常，k-1值超过n/k），那么我们不需要第二遍。但是，当原始问题具有k=21 个保证多数时，我们无法知道我们是否“应该”将其概括为保证 1 个这样的元素或保证k-1。保证越强，问题越容易。

Answer 2

使用 Boyer-Moore 多数投票算法，我们得到：

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Answer 3

您可以使用选择算法来查找 n/3 位置和 2n/3 中的数字。

n1=Selection(array[],n/3);
n2=Selection(array[],n2/3);
coun1=0;
coun2=0;

for(i=0;i<n;i++)
{
    if(array[i]==n1)
      count1++;
    if(array[i]==n2)
      count2++;
}
if(count1>n)
   print(n1);
else if(count2>n)
   print(n2);
else
   print("no found!");

Answer 4

在第 5 行，该if语句应该再进行一次检查：

if(n!=b && (cnt1 == 0 || n == a))

Answer 5

我使用下面的 Python 解决方案来讨论算法的正确性：

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        if nums is None:
            return None
        if len(nums) == 0:
            return None

        num1 = None
        num2 = None
        count1 = 0
        count2 = 0

        # Loop 1
        for i, val in enumerate(nums):
            if count1 == 0:
                num1 = val
                count1 = 1
            elif val == num1:
                count1 += 1
            elif count2 == 0:
                num2 = val
                count2 = 1
            elif val == num2:
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1


        count1 = 0
        count2 = 0

        for val in nums:
            if val == num1:
                count1 += 1
            elif val == num2:
                count2 += 1

        if count1 > count2:
            return num1

        return num2

首先，我们需要证明声明 A：

声明 A：考虑一个列表C，其中包含多次m出现的多数数floor(n/3)。从 3 个不同的数字中删除后C，我们有C'. m是 的多数数C'。

证明：R用于表示m中的出现次数C。我们有R > floor(n/3). R > floor(n/3)=> R - 1 > floor(n/3) - 1=> R - 1 > floor((n-3)/3)。用于R'表示m中的出现次数C'。并用n'来表示 的长度C'。由于删除了 3 个不同的数字，我们有R' >= R - 1. 并且n'=n-3很明显。我们可以R' > floor(n'/3)从R - 1 > floor((n-3)/3). m多数数也是如此C'。

现在让我们证明loop 1. 定义L为count1 * [num1] + count2 * [num2] + nums[i:]。用于m表示多数数。

不变的

多数数m在L.

初始化

在第一次迭代开始时，L是nums[0:]. 所以不变量是微不足道的。

维护

1. if count1 == 0分支：迭代前，L是count2 * [num2] + nums[i:]. 迭代后，L是1 * [nums[i]] + count2 * [num2] + nums[i+1:]。换句话说，L没有改变。所以保持不变。

2. if val == num1分支：迭代前，L是count1 * [nums[i]] + count2 * [num2] + nums[i:]. 迭代后，L是 (count1+1) * [num[i]] + count2 * [num2] + nums[i+1:]。换句话说，L没有改变。所以保持不变。

3. f count2 == 0分支：类似于条件1。
4. elif val == num2分支：类似于条件 2。
5. elsebranch: nums[i]，num1并且num2在这种情况下彼此不同。迭代后，L是(count1-1) * [num1] + (count2-1) * [num2] + nums[i+1:]。换句话说，三个不同的数字从 中移出count1 * [num1] + count2 * [num2] + nums[i:]。从索赔 A 中，我们知道m是 的多数数L。因此保持不变。

终止

当循环终止时，nums[n:]为空。L是count1 * [num1] + count2 * [num2]。

因此，当循环终止时，多数数是num1or num2。

Answer 6

如果数组中有 n 个元素，并且假设在最坏的情况下只有 1 个元素重复 n/3 次，那么选择一个不是重复 n/3 次的数字的概率将为 (2n/3 )/n 即 1/3 ，所以如果我们从大小为“n”的数组中随机选择 N 个元素，那么我们最终选择 n/3 次重复数的概率将至少为 1-(2/3) ^N 。如果我们将其等同于 99.99% 的成功概率，对于任何“n”值，我们将得到 N=23。

因此，只需从列表中随机选择 23 个数字并计算它们的出现次数，如果我们得到大于 n/3 的计数，我们将返回该数字，如果在随机检查 23 个数字后没有得到任何解决方案，则返回 -1；

该算法本质上是 O(n) 因为值 23 不依赖于 n(size of list) ，所以在算法的最坏情况下我们必须遍历数组 23 次。

在 interviewbit(C++) 上接受的代码：

  int n=A.size();
  int ans,flag=0;
  for(int i=0;i<23;i++)
  {

int index=rand()%n;
int elem=A[index];
int count=0;
for(int i=0;i<n;i++)
{
    if(A[i]==elem)
    count++;
}

if(count>n/3)
{
    flag=1;
    ans=elem;
}

if(flag==1)
break;
}

if(flag==1)
 return ans;
else return -1;
 }