在给定所有其他数字的情况下,找到仅在数组中出现一次的数字的算法会出现两次

Question

我能想到的是:

ALGO:

1. 有一个哈希表,用于存储数字及其相关计数
2. 解析数组并增加数字的计数.
3. 现在解析哈希表以获得计数为1的数字.

你能想到比这更好的解决方案吗？使用O(n)运行时并且不使用额外的空间

Answer 1

假设您可以XOR使用数字,这是关键,我相信,因为以下属性:

• XOR 是可交换的和联想的(所以它完成的顺序是无关紧要的).
• XOR与自身编号的编号始终为零.
• 零XOR编号将是一个数字.

因此,如果你只是将XOR所有的值放在一起,那么两次出现的所有值都将相互抵消(给出0),剩下的一个数字(n)将XOR用该结果(0)给出n.

r = 0
for i = 1 to n.size:
    r = r xor n[i]
print "number is " + r

不需要哈希表,这具有O(n)性能和O(1)额外空间(只是一个小的小整数).

Answer 2

Ruby中的答案,假设有一个单例,而其他所有单个外观:

def singleton(array)
  number = 0
  array.each{|n| number = number ^ n}
  number
end

irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3

顺便说一句,^是按位XOR运算符.XOR一切!哈哈哈!

Rampion让我想起了注入方法,所以你可以在一行中完成:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

Answer 3

"解析数组并增加数字的计数."

您可以将其更改为"解析数组,如果哈希表中已存在该数字,则从哈希表中删除该数字".然后第3步就是"获取哈希表中剩余的唯一数字"

Answer 4

给定一个整数数组,除了一个元素外,每个元素都会出现两次.找一个单一的.我们可以使用XOR操作.因为每个数字都是XOR本身,结果将为零.因此,我们对数组中的每个整数进行异或,结果是我们想要找到的单个整数.这是java版本代码:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}

跟进1:给定一个整数数组,每个元素出现三次,除了一个.找一个单一的.注意:您的算法应具有线性运行时复杂性.你能不用额外的内存来实现吗？对于这个问题,我们不能使用XOR操作.解决这个问题的最好方法是使用"位数".创建一个32长度的int数组计数[32].count [i]表示所有整数的第i位中有多少'1'.如果count [i]可以除以3,那么我们忽略这个位,否则我们取出这个位并形成结果.Below是java版本代码:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        int[] count=new int[32];
        for(int i=0;i<32;i++){
            for(int j=0;j<A.length;j++){
                if(((A[j]>>i)&1)==1){
                    count[i]=count[i]+1;
                }
            }
            if((count[i]%3)!=0){
                res=res|(1<<i);
            }
        }
        return res;
    }
}

后续2:给定一个整数数组,除了两个元素外,每个元素都会出现两次.找到两个整数.解答:首先,对数组中的所有整数进行XOR我们可以得到一个结果.(假设它是c)其次,从最低有效位到最高有效位,找到第一个'1'位置(假设位置是p).第三,将整数分为两组,p组在一组中为"1",在另一组中为"0".第四,对两组中的所有整数进行异或,结果是我们想要的两个整数.