本文共 1528 字，大约阅读时间需要 5 分钟。

题目：总共n个元素，求超过n/k个的元素（占一定概率的元素），k=2,3,...

当k==2 时， moore voting algorithm：

用ret=nums[i],count计数，遍历nums，当nums[i]==ret时，count加1，当nums[i]！=ret时，count减1，count==0时，ret重新赋值nums[i];假设超过n/2的数一定存在，则返回 ret;

当k>2时，易得所求元素最多个数为n/k - 1，Linear-time Iceberg Query Algorithm：

第一步，查找候选元素：

若A[i]已在候选表中，即存在c使得，那么f(c) += 1。 若A[i]不在候选表中，且候选表仍有空位，即，那么将A[i]插入到表中，且f(A[i]) = 1。 若A[i]不在候选表中，且候选表已满。那么丢弃A[i]，且对于候选表中每一元素，做f(c) -= 1。该操作完毕之后，所有f(c)归零的元素从候选表中移除。

第二步，遍历nums，判断候选表中的元素是否满足条件

第一题：

int majorityElement(int num[], int n) {    int ele, count = 0, i;	for (i = 0; i < n; i++)	{		if (count == 0){			ele = num[i];			count = 1;		}		else{			if (ele == num[i]){				count++;			}			else{				count--;			}		}	}	return ele;}

第二题：

int* majorityElement(int* nums, int numsSize, int* returnSize) {    int *ret = (int*)malloc(2 * sizeof(int));	int count[2];		int i;	count[0] = 0; count[1] = 0;	for (i = 0; i < numsSize; i++)	{				if (count[0] != 0 && nums[i] == ret[0]){			count[0]++;		}		else if (count[1] != 0 && nums[i] == ret[1]){			count[1]++;		}		else if (count[0] == 0){			ret[0] = nums[i];			count[0]++;		}		else if (count[1] == 0){			ret[1] = nums[i];			count[1]++;		}		else{			count[0]--;			count[1]--;		}	}	count[0] = 0, count[1] = 0;	for (i = 0; i < numsSize; i++)	{		if (nums[i] == ret[0])			count[0]++;		else if (nums[i] == ret[1])			count[1]++;	}	*returnSize = 0;	if (count[0] >numsSize/3){		(*returnSize) ++;	}	if (count[1] > numsSize / 3){		ret[*returnSize] = ret[1];		(*returnSize)++;	}	return ret;}

备注：①判断条件可以简化，更美观，不过对效率应该影响不大

  ②这个算法只会应用，原理证明忽略。。

转载地址：http://shovi.baihongyu.com/