在整数数组中查找第一个非重复数 [英] Finding first non-repeating number in integer array

问题描述

我有一个考试题目：

给定一个整数数组，找到第一个数字， N）时间复杂度和O（1）空间复杂性。

Given an integer array find the first number which is not repeating in array using O(N) time complexity and O(1) space complexity.

我想不出任何解决方案。我知道我可以迭代数组和维护一个linkedhashmap，它将存储数组元素和出现的次数，然后到最后我必须搜索hashmap找到该数字。空间复杂性大于O（1），但我不能想到其他解决方案。

I couldn't think of any solution. I know I can iterate over the array and maintain a linkedhashmap which will store both array element and number of times it appears and then in the end I have to search hashmap to find that number. Space complexity is greater than O(1) but I couldn't think of other solution.

我也仔细阅读问题，并说阵列的最大大小将是100万。我想如果我们可以创建一个定制的hashmap，它将利用一个100万大小的固定大小的数组，那么这可以在O（1）空间复杂性实现，因为在那种情况下，存储需要是不变的，但是如果我是正确的。如果有任何其他解决方案，请让我知道。

I also read problem carefully and the said that max size of array would be 1million. I think if we can create a custom hashmap which will utilise an fixed size array of 1 million size then this can be achieved in O(1) space complexity as in that case storage required would be constant but nore sure if I am correct. Please let me know if there is any other solution.

推荐答案

如果除了一个元素之外，所有元素都有两个（或2的倍数）重复，可以使用XOR运算符。

If there are exactly TWO (or in multiples of 2) entries for all elements except one element, which will be non-repeating, you can use XOR operator.

示例：

int x=arr[0];
for(i=1;i<1000;i++)
  x^=a[i];
printf("Non-repeating: %d",x);

与自身异或的任何数字为0.因此，如果任何数字出现两次，总体XOR结果，因此只留下 x 中的非重复数字。

Any number XORed with itself is 0. So, if any number appears twice it will be 0 in the overall XOR result, thus leaving only the non-repeating number in x.

注意：数字，存储XOR结果的变量必须足够大。

Note: If you have 1 million numbers, the variable to store the XOR result must be large enough.

这篇关于在整数数组中查找第一个非重复数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！