矩阵二分乘求解递推数列
最长递增子序列

Majority Vote Algorithm

Jimmy posted @ 2011年10月12日 16:04 in Others , 3391 阅读

一个学妹问我的问题,让设计时间复杂度为O(nlogn)的算法,找出数组中出现次数超过数组长度一半的值。上网搜了之后发现,其实有更好的解法,Boyer and Moore's Voting Algorithm,降低时间复杂度到O(n)。

1.递归解法(Recursive Method)

function majority ( array A with numer_of_elements N)
{
    if N == 1:
        return A[0]
    let AL, AR be the first halves of A
    let ML = majority(AL)
    let MR = majority(AR)
    if neither half has a majority:
    	return "no majority"
    else:
	check whether either ML or MR is a majority element of A
        if so: return that element
        else: return "no majority"
}

时间复杂度:O(N*logN)

2. Boyer and Moore's Voting Algorithm

#include <stdio.h>
#include <stdlib.h>

int candidate_element(int *array, int n)
{
    int count = 1;
    int curr_candidate = 0;
    int i;
    for(i=0; i<n; i++)
    {
	if(array[i] == array[curr_candidate])
	    ++count;
	else
	    --count;
	if(count == 0)
	{
	    curr_candidate = i;
	    count = 1;
	}
    }
    return array[curr_candidate];
}

int is_majority_element(int *array, int n, int candidate)
{
    int cnt = 0;
    int i;
    for(i=0; i<n; i++)
	if(array[i] == candidate)
	    ++cnt;
    if(cnt > n/2)
	return 1;
    else
	return 0;
}

int main()
{
    int *array;
    int n;
    int i;
    int candidate;
    while(scanf("%d", &n) != EOF)
    {
	array = (int*)malloc(sizeof(int) * n);
        for(i=0; i<n; i++)
	    scanf("%d",array+i);
	
	candidate = candidate_element(array, n);
	if(is_majority_element(array, n, candidate))
	    printf("the majority element is: %d\n", candidate);
	else
	    printf("there is no majority element in the give array\n");
    }
    return 0;
}

时间复杂度:O(N)

形式化证明及分析见此文档: majority vote algorithm.pdf

 

Avatar_small
星海 说:
2011年10月20日 02:42

啊,很巧妙很巧妙。。。。。

Avatar_small
Cooper McLachlan 说:
2018年5月08日 00:15

<!--td {border: 1px solid #ccc;}br {mso-data-placement:same-cell;}--> Algoritham is very important for us to keep right knowledge about algoritham related . Students get rid from writing problems with hire of essay help in australia in professional writers provide perfect progresses to their users.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter