给定一个整数数组,其中一些数字重复1次,一些数字重复2次,只有一个数字重复3次,你如何找到重复3次的数字.不允许使用哈希.算法的复杂度应为O(n)
我假设数组没有排序,或者类似,重复的数字不会出现在一个连续的运行中.否则,问题实际上是微不足道的:只需使用大小为3的窗口扫描数组一次,如果该窗口中的每个数字相同,那么这是在一次连续运行中重复3次的数字.
如果重复分散,则问题变得更加有趣.
由于这是家庭作业,我只会给你一个提示.
这个问题是你给出一组未排序整数的表兄弟,所有数字都出现偶数次,除了出现奇数次的数字.
O(N)通过执行数组中的所有数字的异或,可以很容易地找到该数字; 结果是出现奇数次数.
这有效的原因是x xor x = 0.
例如,3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.