淘先锋技术网

首页 1 2 3 4 5 6 7

只出现一次的数字

给定一个整数数组,除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注:

你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗?

利用异或的性质解决问题

异或:a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

  1. a ⊕ a = 0
  2. a ⊕ b = b ⊕ a
  3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
  4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
  5. a ⊕ b ⊕ a = b.
  6. 若x是二进制数0101,y是二进制数1011;
    则x⊕y=1110
    只有在两个比较的位不同时其结果是1,否则结果为0

即“两个输入相同时为0,不同则为1”!

题干中提到,一个整数数组,除了一个元素只出现一次,其余元素均出现两次。

所以我们可以根据 异或性质 5 来求出结果:

代码实现

public int singleNumber(int[] nums) {

        int num = ;
        for(int i=;i<nums.length;i++){
           num ^= nums[i];  
        }
        return num;
    }