要求空间复杂度O(1)。
思路：方便起见，先假设答案是a。首先我定义3个组，然后取3个数，按照它们3个两两是否相同划分到1~3个组里。接下来我们重复这样的过程：踢一轮、取1个、踢一轮、取1个……
踢是这么操作的：如果这3个组每个组都不空，那么我每个组都踢掉一个，直到出现至少1个空组。这样做是因为如果某一轮我踢掉了一个答案a，那么我一定同时踢掉了2个非a，如果某一轮没有踢a，那我一定踢掉了3个非a。
然后再取1个x：踢完一轮后至少有1个空组，如果x属于某个非空组，就把它放进去，否则就利用那个空组，把空组设为x的组。
这样先踢再取再踢，直到把所有数取完。这时剩下至多2个非空组，所有被踢掉的数中a不超过1/3，所以剩下的数中a不少于1/3，所以如果三组全空，则不存在这样的a，如果只剩下1组，这组所代表的数值就是答案a，如果剩下2组，答案无从确定，再对原数据扫一边从而判断即可。
要求空间复杂度O(1)。 思路：方便起见，先假设答案是a。首先我定义3个组，然后取3个数，按照它们3个两两是否相同...
数组重复元素求值 题目描述： 数组 a[N] 中存放了 1 至 N - 1 个数，其中某个数重复了一次。求找出重复...
求集合的所有子集 对于任意集合A，元素个数为n（空集n=0），其所有子集的个数为2^n个 如集合A={a,b,c}...
字符串与数组 1. 数组重复元素 数组 a[N] 中存放了 1 至 N - 1 个数，其中某个数重复了一次。求找出...
给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。 missing-n...
题目大意 题目链接给你n,p两个数，求n的阶乘中p做为因子出现的个数 分析 如果p为质数的话，很容易求出p出现的次...
题目 给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。 样例N = ...
原题 给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。 样例N = ...
1.题目描述求Sn=1!+2!+3!+4!+5!+…+n!之值，其中n是一个数字(n不超过20)。 2.格式与样例...
给定一个包含 0, 1, 2, ..., n 中 n个数的序列，找出 0 .. n 中没有出现在序列中的那个数。(...
本文标题：求n个数中出现个数超过n/3的元素
本文链接：https://www.haomeiwen.com/subject/razwzftx.html
网友评论