数据结构与算法解析习题2.19：寻找主要元素 Majority Element
题干
,其主元素是一个出现超过N/2的元素。首先找出主元素的一个候选元,第二步确认该候选元是否为主元素。为找出数组A中的候选元,先构造一个数组B,比较A1和A2,如果相等,则放入到数组B中,然后比较A3和A4以此类推,直到比完整个数组A。然后递归地寻找数组B中的候选元,它也是数组A中的候选元。
分析
首先, 这个算法只对偶数成立, 先证明一下算法的正确性:
比如N = 10, 主要元素是3，则3出现的次数>=6
需要证明的点1：6个3随机分布在大小为10的容器中，必定有至少1次的连续下标的2个元素均为3。
反证：任意2个3都不连续（也就是1次都没有）的极端情况是5个3依次被另一个元素隔开：3，1，3，1，3，1，3，1，3，1 所以用第6个3替换1的任意一个的位置，都会出现至少1次连续的2个3。需要证明的点2：连续的两个3出现的位置下标，必定是i2，i2+1
反证：任意2个连续的3的下标都是i*2+1，(i + 1) * 2的极端情况是：1，3，3，1，1，3，3，1，1，3 所以用第6个3替换1的任意一个的位置，都会出现至少1次连续的两个3出现的位置下标，必定是i*2，i*2+1 据此可以证明B数组中一定包含候选元.需要证明的点3：B数组中候选元的个数出现次数>CountB/2
反证：如果B中候选元的个数出现次数<=CountB/2，举个B的极端情况，3，3，3，1，2，4 根据“比较A1和A2，如果它们相等则取其中之一加到数组B中；否则什么都不做”规则反推A，A必定包含3，3，3，3，3，3，1，1，2，2，4，4(这些元素组成的数组我们定义为A的子数组A`，D后面可能还有其他元素，我们定义为A的子数组A``)，分情况讨论:
1：A``的元素个数为0，那么在A中3的个数 = CountA` / 2 + 0 / 2 = CountA/2，A中3的个数不满足>CountA/2的条件。
2：A``的元素个数大于0，最好情况有1半都是3，（因为如果A``的3超过一半，根据证明1和证明2，B中必定会在现有元素基础上多出至少1个候选元3），此时A中3的个数 CountA` / 2+ CountA`` / 2 = CountA/2，A中3的个数不满足>CountA/2的条件。所以B数组中候选元的个数出现次数>CountB/2。
问答
(1)、递归何时停止? 当数组 B 中只有两个或更少的元素时递归便不必要了。 (2)、数组A为奇数情况时如何处理? 一种方法是，注意到如果前 N-1 个元素中有主要元素，则最后一个元素对结果没有影响，否则最后一个元素可能是候选元，将它作为候选元。 (3)、题干所描述的算法的运行时间? 设运行时间为 T(N)，有递推式 T(N)=T(N/2)+O(N)，解得 T(N)=O(N) (4)、如何避免使用附加数组B? 保存一个数组 A 的拷贝后，可将要添加到数组 B 的元素直接覆盖在数组 A 上，每一级 递归均可这样做。最初的递归策略需要 O(logN)个数组，而这样只需要两个。 (5)、给出题干所描述的算法代码? 如下
#include <stdio.h>
#define NotAMainCell -1
#define ARRLength 10
void swap (int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int isMainCell(int arr[], int probablyMaincell) {
int count = 0;
for (int i = 0; i < ARRLength; i++) {
if (arr[i] == probablyMaincell) {
count++;
}
}
if (count > ARRLength / 2) {
return 1;
} else {
return 0;
}
}
int findMainCell(int arr[], int length) {
if (length == 0) {
return NotAMainCell;
}
if (length == 1) {
if (isMainCell(arr, arr[0]) == 1) {
return arr[0];
} else {
return NotAMainCell;
}
}
for (int i = 0, len = 0; i < length; i = i + 2) {
if (arr[i] == arr[i + 1]) {
swap(&arr[i], &arr[len++]);
}
if (i == length - 1) {
return findMainCell(arr, len);
} else if (i == length - 2) {
int resule = findMainCell(arr, len);
if (resule == NotAMainCell) {
if (isMainCell(arr, arr[ARRLength - 1]) == 1) {
return arr[ARRLength - 1];
} else {
return NotAMainCell;
}
} else {
return resule;
}
}
}
return NotAMainCell;
}
int main() {
int arr[ARRLength] = {4,3,4,2,4,4,2,4,3,4};
printf("%d \n", findMainCell(arr, ARRLength));
}
当然还有很多方法找到主元的，比如排序一下，那么index为n/2的元素，必然是主元。用hashmap。还有删除不同的一对元素等。。就不一一展开了。