本文共 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/