2013年41题
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2013年41题
(13 分） 已知—个整数序列 A = (a0, a1, . . . , an−1)，其中 0≤ai < n (0≤i < n)。若存在 ap1 == x 且 m > n/2 (0≤pk < n， 1≤k≤m)，则称 x 为 A 的主元素。例如 A = (0, 5, 5, 3，5, 7, 5, 5)，则 5 为主元素；又如 A = (0, 5, 5, 3, 5, 1, 5, 7)，则 A 中没有主元素。假设 A 中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：(1）给出算法的基本设计思想。(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>预计得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>枚举</td><td rowspan=1 colspan=1>O(n2)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>快速排序</td><td rowspan=1 colspan=1>O(nlogn)</td><td rowspan=1 colspan=1>O(logn)</td><td rowspan=1 colspan=1>13</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>散列表</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>14</td></tr><tr><td rowspan=1 colspan=1>特殊解</td><td rowspan=1 colspan=1>技巧</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>15</td></tr></table>
## 【解法1】暴力解：枚举，分别判断每个数是不是主元素
(1)两层循环：外层循环枚举数组中每个候选元素，内层循环统计该元素在数组中出现的次数，若次数大于n/2则为主元素。（2）伪代码如下：
int ans(int A[], int n)
{
int m; // m统计当前枚举元素出现次数
for (int i=0; i<n; i++)
{
m=0; // 每次换元素的时候m要清零
for (int j=0; j<n; j++)
if (A[i]==A[j])
m++;
if (m>n/2)
return A[i]; //找到了主元素
}
return -1; // 未找到主元素
}
void Qsort(int A[], int L, int R)
{
if (L>=R)
return; //区间≤1,退出
int pivot, i=L, j=R; // i, j 为左右指针
pivot=A[L]; // pivot 为基准
while (i<j){
while (i<j && A[j]>=pivot)
while (i<j && A[i]<=pivot) j--;
i++;
if (i<j)
swap(A[i], A[j]); // A[j]<pivot, A[i]>pivot
}
swap(A[L], A[i]); //基准归位
Qsort(A, L, i-1); //递归处理左区间
Qsort(A, i+1, R); // 递归处理右区间
}
Qsort(A, 0, n-1);
int t=A[(n-1)/2]; // 主元素只可能是A[(n-1)/2]
int m=0; // m统计当前枚举元素出现次数
for (int i=0; i<n; i++)
if (A[i]==t)
m++;
if (m>n/2)
return t; //找到了主元素
return -1; // 未找到主元素
}
int ans(int A[], int n)
{
int count[n]={0};// count统计数字出现频率
for (int i=0; i<n; i++)
count[A[i]]++; // 0<=A[i]<=n，不会越界
for (int j=0; j<n; j++)
if (count[j]>n/2)
return j;//找到了主元素,输出主元素
return -1; ///未找到主元素，输出-1
}
int ans(int A[], int n)
{
int j=A[0], t=1; //取A[0]作为可能主元素
for (int i=1; i<n; i++)
else
{
if(t<0)
j=A[i]; t=1;
}
}
int m=0; //m统计j出现的次数
for (int i=0; i<n; i++)
if (A[i]==j) m++;
if (m>n/2) return j; //j是主元素，输出j
else return -1; //j不是主元素，输出-1
}
void Qsort(int A[], int L, int R, int )
{
if (L>=R)
return; // 区间≤1，退出
int pivot, i=L, j=R; j为左右指针
pivot=A[L]; // pivot 为基准
while (i<j){
while (i<j && A[j]>=pivot)
j--;
while (i<j && A[i]<=pivot)
i++;
if (i<j)
swap(A[i], A[j]); // A[j]<pivot, A[i]>pivot
}
swap(A[L], A[i]); //基准归位 首
Qsort(A, L, i-1); //递归处理左区间
Qsort(A, i+1, R); // 递归处理右区间
}
void ans(int A[], int n)
{
Qsort(A, 0, n-1);
输出A1:A[0~n/2-1]
输出A2:A[n/2~n-1] //奇数时中间数分给A2
}
void Quick_Select(int A[], int L, int R, int n)
{
if (L>=R)
return; //区间≤1，退出
int pivot, i=L, j=R; // i,j 为左右指针
while (i<j) pivot=A[L]; // pivot 为基准
{
while (i<j && A[j]>=pivot)
while (i<j && A[i]<=pivot)
i++;
swap(A[i], A[j]); // A[j]<pivot, A[i]>pivot
swap(A[L], A[i]); //基准归位
if (n/2-1==i) break;
if (n/2-1>=L && n/2-1<=i-1)
Quick_Select(A,L,i-1,n); // n/2-1在左区间范围中，选择左区间递归处理
else
Quick_Select(A,i+1,R,n); // n/2-1在右区间范围中，选择右区间递归处理
}
void ans(int A[], int n)
{
Quick_Select(A, 0, n-1, n);
输出A1:A[0~n/2-1]
输出A2:A[n/2~n-1]
}
}
void ans(int A[], int n)
{
int L=0, R=n-1;
while (L<R){ // 类快排划分过程
int pivot, i=L, j=R; // i, j 为左右指针
pivot=A[L]; // pivot 为基准
while (i<j){
while (i<j && A[j]>=pivot)
j--;
i++;
if (i<j)
swap(A[i], A[j]); // A[j]<pivot, A[i]>pivot
}
swap(A[L], A[i]); //基准归位
if (n/2-1==i) break; //分成所需要的两个区间
if(n/2-1>=L && n/2-1<=i-1) R=i-1; // n/2-1在左，改右边界
else L=i+1; // n/2-1在右，改左边界
}
输出A1:A[0~n/2-1]
输出A2:A[n/2~n-1] /1奇数时中间数分给A2
}
int ans(int A[], int n)
{
for (int i=1; i<=n+1; i++)
{
bool flag=false; //先假设i未出现
for (int j=0; j<n; j++)
if (i==A[j])
flag=true; // 此时i出现了，flag变成true
if (flag==false) // 若i未出现过则输出i
return i;
}
}