如何找到在不出现两次的阵列的唯一编号 [英] How to find the only number in an array that doesn't occur twice

问题描述

下面是从面试：

在一个给定的数组，其中包含整数，每个数字重演   一旦除了一，不重复。编写一个函数，发现   不重复的次数。

In a given array, which contains integers, each number repeats itself once except for one, which doesn't repeat. Write a function that finds the number that doesn't repeat.

我想过用一个HashSet的，但也可能复杂化的一切......

I thought about using an HashSet, but it might complicate everything...

一个简单的解决方案，任何想法？

Any ideas of a simple solution?

推荐答案

您可以定义一个整数结果初始化为0，然后通过应用XOR逻辑您的阵列中的所有元素做一些位操作。

You can define an integer "result" initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.

最后，结果将等于只出现一次的唯一元素。

At the end, "result" will be equal to the only element that appears only one time.

result = 0
for i in array:
  result ^= i
return result

<一个href="http://en.wikipedia.org/wiki/Bitwise_operation#XOR">http://en.wikipedia.org/wiki/Bitwise_operation#XOR

有关例如，如果您的阵列包含的元素[3，4，5，3，4]，算法将返回

For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return

3 ^ 4 ^ 5 ^ 3 ^ 4

3 ^ 4 ^ 5 ^ 3 ^ 4

但XOR运算符^是联想和交换，这样的结果也将是等于：

But the XOR operator ^ is associative and commutative, so the result will be also equal to:

（3 ^ 3）^（4 ^ 4）^ 5

(3 ^ 3) ^ (4 ^ 4) ^ 5

由于I ^ I = 0的任意整数i和I ^ 0 =我，你有

Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have

（3 ^ 3）^（4 ^ 4）^ 5 = 0 ^ 0 ^ 5 = 5

(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

这篇关于如何找到在不出现两次的阵列的唯一编号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！