136. Single Number 找数组只出现一次的数字

本文主要是介绍136. Single Number 找数组只出现一次的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路:这道题不像之前的540. Single Element in a Sorted Array是有序序列,更复杂.
(看讨论的)用异或(XOR,或记为⊕)
以下结论很吊很有用:

0 ⊕ A = A //A为任意数
A ⊕ A = 0
即,任意数与0相与都等于其自身,任意数与其自身异或都为0补充:
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)  //结合律
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D  //可以去掉括号
A ⊕ B ⊕ C ⊕ D = A ⊕ C ⊕ B ⊕ D  //可以随意交换
即,只要参与异或运算的成员不变,任意交换异或顺序,结果都一样

之前在(https://www.jianshu.com/p/99d87c778b24)推导过的结论也可以由上述结论推出:

若f ⊕ m = G,则:
f ⊕ G = m //推导: f ⊕ G = f ⊕ (f ⊕ m) = f ⊕ f ⊕ m = 0 ⊕ m = m)
m ⊕ G = f //同上

综上所述,数组中若存在重复两次的数i,则其异或结果必为0.因此遍历数组,将所有元素异或,最后剩下的必定是出现单次的数.

int singleNumber(vector<int>& nums) {for (int i = 1; i < nums.size(); i++) {  //遍历数组nums[0] ^= nums[i];  //直接用第0号存储异或结果,节省空间}return nums[0];
}

py

class Solution:def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""res = nums[0]for i in range(1, len(nums)):res ^= nums[i]return res

这篇关于136. Single Number 找数组只出现一次的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---