由于整数,其中一些号码重复1次的数组,有的号码重复2次,只有一个号码重复3次,你怎么发现重复3次的号码。使用哈希是不允许的。算法的复杂性应为O(n)
Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. Using hash was not allowed. Complexity of algorithm should be O(n)
推荐答案我假设数组没有排序,或者类似地,一些重复不会出现在一个连续运行。否则,这个问题实在是微不足道的。只是扫描阵列一旦大小为3的窗口,如果在该窗口中的每个数字都是一样的,那么这是一个重复3次在一个连续运行数
I assume the array is not sorted, or similary, repeats of a number don't appear in one contiguous run. Otherwise, the problem is really trivial: just scan the array once with a window of size 3, and if each number in that window is the same, then that's the number that repeats 3 times in one contiguous run.
如果在重复分散,那么这个问题就变得更有趣了。
If the repeats are scattered, then the problem becomes more interesting.
由于这是功课,我只会给你一个提示。
Since this is homework, I will only give you a hint.
这问题出在哪里,你只能给无序整数数组的表弟,和所有的数字出现偶数的时候,一个出现的次数为奇数的除外。
This problem is a cousin of where you're given an array of unsorted integers, and all numbers appear an even number of times, except one that appears an odd number of times.
这个数字可以很容易地在 O(N)通过执行中的异或阵列中的所有号码;其结果是出现的次数为奇数的数目
That number can be found quite easily in O(N) by performing an exclusive-or of all the numbers in the array; the result is the number that appears an odd number of times.
之所以说这个作品是 X XOR X = 0 。
因此,例如, 3 XOR 4 XOR 7 XOR 0 XOR 4 XOR 0 XOR 3 = 7 。
更多推荐
鉴于整数,其中一些号码重复1次的数组,有的号码重复2次,只有一个号码重复3次,你怎么发现重复3次的号码
发布评论