对于异或运算的初步认识与auto用法

博主：本当迷
发布时间：2021 年 09 月 03 日
2130 次浏览
5 条评论
1008字数
分类：编程例题

今天遇到了一道题！题目如下：

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

说明：

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

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 我的思路：

给数组使用快速排序法，然后用双指针遍历数组，前后不相同的数即为目标值！

快速排序法时间复杂度O（log n）, 遍历数组 O（n）,显然已经不符合题意 ->算法应该具有线性时间复杂度。（O（n））。

思来想去想不到解决方法！

我偷看了一些评论，评论说用到异或运算，以前没有接触过，于是我决定查看官方答案！

## 答案：

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};
```

### 异或运算：

`^ ` 这个运算符叫 `异或运算符`

异或运算有以下三个性质。

任何数和 0 做异或运算，结果仍然是原来的数，即：a ^0 = a;
任何数和其自身做异或运算，结果是 0，即：a^a = 0;
异或运算满足交换律和结合律，即：a^a^0^a = a;

### auto的用法：

`for (auto x : nums)`

作用：遍历数组nums，并且每一次遍历得到的值 赋值给 x；

相当于：

```cpp
for(int i = 0; nums[i] != '\0'; i++)
{
	int x = nums[i];
} 
```

最后修改：2021 年 09 月 14 日

如果文章有用，请随意打赏。

5 条评论

任广洲 ViVO Android 11
November 17th, 2021 at 11:49 am

回复
1. 本当迷 QQ浏览器 10.8.4455.400 Windows 10
  November 18th, 2021 at 10:52 am
  
  @任广洲
  
  回复
梦一帆 Google Chrome 92.0.4515.107 Windows 10
September 3rd, 2021 at 03:57 pm

for (auto x : nums) 是C11，dev c++ 默认c99. (ó﹏ò｡)
我就说我以前从来没用过

回复
梦一帆 Google Chrome 92.0.4515.107 Windows 10
September 3rd, 2021 at 03:53 pm

auto 的作用仅仅是判断初始化右值的类型，让左值匹配。不是“遍历数组nums，并且每一次遍历得到的值赋值给 x”。for (auto x : nums)才是这个功能
for(int x:nums)，也是可以的，只是auto x 判断了x的类型，在预处理的时候判断的，不会影响运行时间。
在C++ 容器里面常用，因为有些容器类型比较长。

回复
1. 本当迷 QQ浏览器 10.8.4455.400 Windows 10
  September 3rd, 2021 at 06:19 pm
  
  @梦一帆
  
  牛蛙！get到了！
  
  回复