LeetCode进阶136-位运算巧用（leetcode146）

概要

有过开发经验的童鞋可能已经注意到，很多时候在Java标准库的源码中可以看到位运算的身影，本质原因是位运算能提高算法效率。在之前发布的博文中曾提到过原因LeetCode进阶-彩蛋一，也有一些实际运用的例子，比如按位与&判断奇偶数LeetCode进阶-1025（动态规划)，移位<<(>>)和&结合存储数据存取LeetCode进阶-1029（贪心）。本篇将结束位运算中的异或运算^的巧妙用法。

原题

136. Single Number （Easy)

Given a non-empty 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?

Example 1:

Input: [2,2,1]

Output: 1

Example 2:

Input: [4,1,2,1,2]

Output: 4

• tag: Bit Manipulation

136. 只出现一次的数字 (简单）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

• 分类：位运算

题意分析&&思路设计

根据题意，需要找出数组中唯一的没有重复出现的整数。由于本篇是位运算实践科普篇，在分析之前先来看下^异或运算符的特性：第一个操作数的的第n位于第二个操作数的第n位 相反，那么结果的第n为也为1，否则为0。简单来说^运算有两个比较典型的应用特性：1、相同数字（整数）进行^运算结果为0。假设a=b,由于a和b每一位上的数字相同，因此最终a^b=0，结合本题。2、任何数字（整数）异或0，即n^0=n，同理可得。除了一个数字只出现了一次，其他任何数都出现两次。也就是[a,a,b,b,c,c...x,d,d,e,e..]（列举示例，实际顺序忽略）中找出只出现一次的x。显然依次将所有数字进行^运算，利用相同数字n^n=0,x^0=x特点最后计算结果必然为只出现了一次的整数。

编码实践

public int singleNumber(int[] nums) {

int res = 0;

int len = nums.length;

for (int i = 0; i < len; i++) {

res ^= nums[i];

}

return res;

}

结语

本题属于位运算科普篇，属于位运算的基本技巧。最后，如果觉得本文对你有所帮助或启发那就来个赞吧0.0～