力扣-136-数组中唯一一个不重复的元素

评论

题目：
136. Single Number(easy)

题目大意：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

1
2
3
4
5
6
7
示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

解题思路：
刚开始拿到本题，想到用哈希表存数，虽然时间复杂度是O(n)，但是空间复杂度也是O(n)，不满足题目要求——不使用额外空间。
没有想到，查看了题解中提到了异或的位运算方法，,很巧妙，记录一下。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Java:
public int singleNumber(int[] nums){
    int ans = 0;
    for(int num : nums){
        ans ^= num;
    }
    return ans;
} 

/*
既满足时间复杂度又满足空间复杂度，就要提到位运算中的异或运算 XOR，主要因为异或运算有以下几个特点：

一个数和 0 做 XOR 运算等于本身：a⊕0 = a
一个数和其本身做 XOR 运算等于 0：a⊕a = 0
XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

作者：guanpengchn
链接：https://leetcode-cn.com/problems/single-number/solution/hua-jie-suan-fa-136-zhi-chu-xian-yi-ci-de-shu-zi-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

InstantCWeedStudent

个人简介。