赞
踩
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
- 输入:nums = [2,2,1]
- 输出:1
-
- 输入:nums = [4,1,2,1,2]
- 输出:4
-
- 输入:nums = [1]
- 输出:1
使用位运算的异或运算来解答
异或:当两个操作数的二进制表示形式的对应位不同时,结果为1,否则结果为0
任何数和 0 做异或运算
任何数和自身做异或运算,结果为 0
异或遵循结合律 a ^ b ^ c = a ^ (b ^ c),同一堆数,不管异或计算顺序如何变化,异或一定是相同结果
- class Solution {
- public:
- int singleNumber(vector<int>& nums) {
- //其余元素均只出现两次
- int res = 0;
- for (int num: nums) {
- res = num ^ res;
- }
- return res;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。