> 电器
异或运算的规则(异或运算什么意思)
导语:异或运算的妙用
LeetCode No.136 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
解法:时间复杂度为O(N),不开辟新的内存空间。根据题眼,“其余每个元素均出现两次”,可以联想到位运算中的「异或」,它的Java表示为^,规则是:「相异置1,相同置0,0与任何数异或结果为任何数」。这样,我们就可以用0与数组中的每个元素异或,与第一个元素异或的结果一定为第一个元素,如果后续有和第一个元素相同的元素,那么结果重新置为0。那么,最终循环结束得到的结果就是题目所求。
代码如下:
class Solution { public int singleNumber(int[] nums) { int res = 0; for(int num : nums){ res ^= num; } return res; }}
运行结果:
成功执行用时: 1 ms, 在Single Number的Java提交中击败了99.44% 的用户内存消耗: 28.6 MB, 在Single Number的Java提交中击败了33.50% 的用户
免责声明:本站部份内容由优秀作者和原创用户编辑投稿,本站仅提供存储服务,不拥有所有权,不承担法律责任。若涉嫌侵权/违法的,请与我联系,一经查实立刻删除内容。本文内容由快快网络小德创作整理编辑!