算法 寻找多数元素

寻找多数元素

一、问题描述：

令A[1.....n]是一个整数序列，A中的整数a如果在A中出现的次数多于[n/2]次，那么a就称为多数元素。例如在序列1，3，2，3，3，4，3中，3是多数元素，应为7个元素中它出现的次数是4。有几种方法可以解决这个问题。

法【1】：蛮力算法

把每一个元素和其他元素比较，并且对每个元素计数，如果，

某个元素的计数大于[n/2]，就可以断言它是多数元素；否则，在序列中就没有多数元素。但是，这样的比较次数是n(n-1)/2=Θ(n²),这种方法的代价太昂贵。所以称为蛮力算法。 

法【2】：排序算法 

另外一种比较有效地算法是，对这些元素排序，并且计算每个

元素在序列中出现多少次。这在最坏的情况下的代价是Θ（n log n）。因为在最坏情况下，排序这一步需要Ω（n log n）次比较。 

法【3】：中间元素法 

另外一种算法是寻找中间元素，就是第[n/2]元素。因为多数

元素，在排序的序列中一定是中间元素，可以扫描这个序列来测试中间元素是否确实是多数元素。由于中间元素可以在Θ(n)时间内找到，这个方法要花费Θ（n）时间。

二、算法分析：

通过归纳法导出一个漂亮算法，可以很好的解决这个问题。

1、该算法基于以下结论：

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

2、接下来是其算法过程：

将计数器置1，并令c=A[1]，从A[2]开始，逐个地扫描元素，如果被扫描的元素和c相等，则计数器加1；如果元素不等于c，则计数器减1；如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者。如果在c和A[j]（1<j<n）比较时计数器为0，那么对于A[j+1，，，n]上的元素递归调用candidate过程。注意减少计数器就是以上的观察结论中所诉去除两个不同元素的思想的实现。

3、伪代码形式如下：

算法：MAJORITY

输入：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>[n/2]   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)

三、源代码（c++）：

#include<iostream>

using namespace std;

int candidate(int);

int *A;

int n;

int main()

{

cout<<"input n is:";

cin>>n;

A=new int[n+1];

cout<<"input n element!"<<endl;

for(int i=1;i<=n;i++)

{

cout<<"# "<<i<<" element is: ";

cin>>A[i];

}

int c,count=0;

c=candidate(1);

for(int j=1;j<=n;j++)

{

if(A[j]==c)

count++;

}

if(count>(n/2))  //check again,c is the majority element 

cout<<"the majority element in array is: "<<c<<endl;

else

cout<<"none!";

delete[] A;

return 0;

}

int candidate(int m)

{

int j,c,count;

j=m;c=A[m];count=1;

while(j<n&&count>0)

{

j++;

if(A[j]==c)

count++;

else

count--;

}

if(j==n)

return c;

else

return candidate(j+1);

}

四、分析迭代过程：

输入的序列为0,5,1,0,0,0,5,0.  n=8

Candidate(1)

 j=1,c=0,count=1

 j=2,A[2]=5(!=c),count=0

Candidate(3)

 j=3,c=1,count=1

 j=4,A[4]=0(!=c),count=0

Candidate(5)

 j=5,c=0,count=1

 j=6,A[6]=0(=c),count=2

 j=7,A[7]=5(!=c),count=1

 j=8,A[8]=0(=c),count=2

j=n     return c (c=0)

算法 寻找多数元素

寻找多数元素

一、问题描述：

令A[1.....n]是一个整数序列，A中的整数a如果在A中出现的次数多于[n/2]次，那么a就称为多数元素。例如在序列1，3，2，3，3，4，3中，3是多数元素，应为7个元素中它出现的次数是4。有几种方法可以解决这个问题。

法【1】：蛮力算法

把每一个元素和其他元素比较，并且对每个元素计数，如果，

某个元素的计数大于[n/2]，就可以断言它是多数元素；否则，在序列中就没有多数元素。但是，这样的比较次数是n(n-1)/2=Θ(n²),这种方法的代价太昂贵。所以称为蛮力算法。 

法【2】：排序算法 

另外一种比较有效地算法是，对这些元素排序，并且计算每个

元素在序列中出现多少次。这在最坏的情况下的代价是Θ（n log n）。因为在最坏情况下，排序这一步需要Ω（n log n）次比较。 

法【3】：中间元素法 

另外一种算法是寻找中间元素，就是第[n/2]元素。因为多数

元素，在排序的序列中一定是中间元素，可以扫描这个序列来测试中间元素是否确实是多数元素。由于中间元素可以在Θ(n)时间内找到，这个方法要花费Θ（n）时间。

二、算法分析：

通过归纳法导出一个漂亮算法，可以很好的解决这个问题。

1、该算法基于以下结论：

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

2、接下来是其算法过程：

将计数器置1，并令c=A[1]，从A[2]开始，逐个地扫描元素，如果被扫描的元素和c相等，则计数器加1；如果元素不等于c，则计数器减1；如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者。如果在c和A[j]（1<j<n）比较时计数器为0，那么对于A[j+1，，，n]上的元素递归调用candidate过程。注意减少计数器就是以上的观察结论中所诉去除两个不同元素的思想的实现。

3、伪代码形式如下：

算法：MAJORITY

输入：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>[n/2]   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)

三、源代码（c++）：

#include<iostream>

using namespace std;

int candidate(int);

int *A;

int n;

int main()

{

cout<<"input n is:";

cin>>n;

A=new int[n+1];

cout<<"input n element!"<<endl;

for(int i=1;i<=n;i++)

{

cout<<"# "<<i<<" element is: ";

cin>>A[i];

}

int c,count=0;

c=candidate(1);

for(int j=1;j<=n;j++)

{

if(A[j]==c)

count++;

}

if(count>(n/2))  //check again,c is the majority element 

cout<<"the majority element in array is: "<<c<<endl;

else

cout<<"none!";

delete[] A;

return 0;

}

int candidate(int m)

{

int j,c,count;

j=m;c=A[m];count=1;

while(j<n&&count>0)

{

j++;

if(A[j]==c)

count++;

else

count--;

}

if(j==n)

return c;

else

return candidate(j+1);

}

四、分析迭代过程：

输入的序列为0,5,1,0,0,0,5,0.  n=8

Candidate(1)

 j=1,c=0,count=1

 j=2,A[2]=5(!=c),count=0

Candidate(3)

 j=3,c=1,count=1

 j=4,A[4]=0(!=c),count=0

Candidate(5)

 j=5,c=0,count=1

 j=6,A[6]=0(=c),count=2

 j=7,A[7]=5(!=c),count=1

 j=8,A[8]=0(=c),count=2

j=n     return c (c=0)