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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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}。

img

附件

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

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道