首页 > 代码库 > 在数组中寻找主要元素
在数组中寻找主要元素
来自：《数据结构与算法分析——C语言描述》练习2.19
问题描述：
大小为N的数组A，其主要元素是一个出现次数超过N/2的元素（从而这样的元素最多有一个）。例如，数组
3，3，4，2，4，4，2，4，4 有一个主要元素4，而数组
3，3，4，2，4，4，2，4 没有主要元素。
题目给了一种递归的算法，不过不太理解。看了几位前辈的代码之后换了思路。下面是我的理解：
第一步，寻找候选元素。遍历数组元素，获得第一个元素将其写入ele，标记为1；接下来访问下一元素，如果它与ele相等，标记+1，否则-1。当ele减小到0时，继续读入下一元素到ele，并将标记重设为1。继续下去，直到最后一个元素。此时，ele获得出现次数最多的元素。
第二步，确定该元素是否主要元素。这个不难，用计数器统计该元素在数组中的出现次数count。如果count超过半个数组大小，该候选元素就是主要元素，返回即可；否则返回NOTFOUND。
时间复杂度显然是O（N）。
1 int findCandidate(const int A[], int N) 2 { 3 int i, mark, ele; 4 5 mark = 0; 6 for (i = 0; i < N; i++) 7 { 8 if (mark == 0) 9 {10 mark = 1;11 ele = A[i];12 }13 else if (A[i] == ele)14 mark++;15 else16 mark--;17 }18 return ele;19 20 }21 22 int findMajority(const int A[], int N)23 {24 int ele, i, count;25 26 count = 0;27 ele = findCandidate(A, N);28 for (i = 0; i < N; i++)29 if (A[i] == ele)30 count++;31 if (count > N / 2)32 return ele;33 return NOTFOUND; //NOTFOUND is -134 }
在数组中寻找主要元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。