Majority

问题描述

A[1…n] 是一个整数序列，A中的整数a如果在A中的出现的次数大于N/2,那么a成为多数元素。例如,在序列 1,3,2,3,3,4,3 中,3是多数元素,因为 7 个元素中它出现 4 次。现在我们就要讨论如何利用计算机来找出一个序列中的多数元素,当然这个多数元素要么不存在,要么就只有一个。

算法描述

观察结论：在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新的序列中还是多数元素。

算法输入：n个元素的数组A[1…n]

算法输出：若存在多数元素，则输出；否则输出none

1. c←candidate(1)
2. count←0
3. for j←1 to n
4. if A[j]=c then count←count+1
5. end for
6. if count >/2n then return c
7. else return none
过程:candidate(m)
1. j←m;c←A[m];count←1
2.while j<n and count >0
3. j←j+1
4. if A[j]=c then count ←count+1
5. else count←count+1
6. end while
7. if j=n then return c
8. else return candidate(j+1)

代码：

#include<stdio.h>
#include<malloc.h>

int main()
{
    int N;
    int *a;
    char *b;
    int i;
    printf("Please input the number of the array:\n");
    scanf("%d",&N);
    a = (int*)malloc(N*sizeof(int));
    printf("Please input the array:\n");
    for (i = 0; i < N; i++)
        scanf("%d", &a[i]);

    int x = majority(a, N);
    printf("%d", x);
}

int majority(int *a, int n)
{
    int c = condidate(a, 0, n);
    static int count = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        if(a[i] == c)
            count = count + 1;
    }
    if(count > (n/2))
        return c;
    else
        return NULL;
}

//一次比较的过程
int condidate(int *a, int m, int n)
{
    int j = m;
    int c = a[m];
    int count = 1;
    while((j < n - 1)&&(count > 0))
    {
        j = j + 1;
        if(a[j] == c)
            count = count + 1;
        else
            count = count - 1;
    }
    if(j == n - 1)
        return c;
    else
        return condidate(a , j+1, n);   //递归调用
}

举例说明：比如a = {1 ,2 ,3 ,2 ,2 , 2, 2 ,4, 5}。

附件

文章中的mmap图的附件在这里