给定一个整数数组，其中一些数字重复1或2次，但一个数字重复3次，您如何找到它？ [英] Given an array of integers where some numbers repeat 1 time or 2 times but one number repeats 3 times, how do you find it?

问题描述

给出一个整数数组，其中一些数字重复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)

推荐答案

我假设数组未排序或相似，重复了数字don不会连续出现。否则，这个问题确实是微不足道的：只需使用大小为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 。

The reason why this works is that x xor x = 0.

例如， 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7 。

这篇关于给定一个整数数组，其中一些数字重复1或2次，但一个数字重复3次，您如何找到它？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！