给定一个2n元素数组，其中n是相似的，n是不同的。
给定n个元素的数组，其中n个元素相同，其余n个元素都不同。编写一个C程序，找出数组中存在n次的值
我按照以下方式思考:比较ai和ai+1，比较ai和ai+2以及返回元素
这将在O(n) time..can中运行，有人给出了更好的解决方案吗？
我正在考虑一些解决办法，上面说的是-
element.
- Majority
- 声明两个变量a)计数变量，以跟踪大多数数组元素的计数。
- 执行for循环并重复步骤4-6直到数组结束。如果当前数组元素等于多数元素，则增量计数
- ，如果计数为0，则用当前数组元素更新多数元素并进行增量计数。如果计数不为0，则使用
<代码>H 113否则，如果计数不为0，则减少计数。H 214H 115再执行一次循环，并计数数组中多数元素的出现次数，如果它是数组大小的一半，那么我们已经找到了多数元素，否则就没有多数元素。
回答 2
Stack Overflow用户
发布于 2011-07-11 20:05:45
您可以使用多数元素算法作为O(n)解具有O(1)空间的基础。
您需要一个存储元素的空间。选择第一个元素并存储它，如果下一个元素与存储的元素相同，您就完成了。如果没有，请从下一步重新启动算法。如果在结束后找不到元素，就意味着元素是成对排列的，如(a，b)，(a，c)，(a，d)或(b，a)，(a，c)，(a，d)，(e，a)。比较前四个元素，您就找到了重复的元素。
因为元素可以是任意顺序的，所以无论哪一个n/2元素，您都可以检查它们是否都是不同的。因此，没有比O(n)更好的解。
Stack Overflow用户
发布于 2012-02-19 06:37:34
这里给出了一种用线性时间多数投票算法(http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)求解最多两次传递和O(1)空间的方法。
选择第一个元素并扫描数组，以确定这是否是重复的元素(扫描剩余数组的一半就足够了)。如果元素是重复元素，那么我们就完成了；如果没有，则在remaning数组中应用线性时间多数表决算法。
我们检查第一个元素的原因是，只有当元素重复数组中的元素数的一半以上时，线性时间多数表决才有效。
https://stackoverflow.com/questions/6655536
复制相似问题
腾讯云开发者
