鉴于整数，其中一些号码重复1次的数组，有的号码重复2次，只有一个号码重复3次，你怎么发现重复3次的号码 [英] 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

问题描述

由于整数，其中一些号码重复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次的号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！