目录

题目描述

具体思路

---

题目描述

原题链接

具体思路

①首先看到数组中重复的数字，想到快慢指针，但是数组的元素是乱序的不好求。因此先对数组排序。使用了STL库的sort函数，时间复杂度O(nlogn)不符合题目要求，空间复杂度O(1)。

//快慢指针+sortint singleNumber(vector<int>& nums) {if(nums.size()==1) return nums[0];sort(nums.begin(),nums.end());if(nums[0]!=nums[1] && nums[1]==nums[2]) return nums[0];//排除第一个项是唯一数的情况int tar=-1;for(int l=0,r=1;r<nums.size()-1;r++){if(nums[l]!=nums[r]){if(nums[r+1]==nums[r]){l=r+1;}else{tar=nums[r];break;}}else{l=r;}}if(tar==-1) tar=nums[nums.size()-1];//排除最后一个项是唯一数的情况return tar;}

②后面研究，发现对于对于查找数组中唯一一个出现一次的元素，我们更适合使用线性扫描和位操作的方法。异或运算满足交换律，且一个数异或自己结果是0，一个数异或0结果是自己。因此把数组中所有元素进行异或运算，得到结果是唯一数

    int singleNumber(vector<int>& nums) {if(nums.size()==1) return nums[0];int ans=nums[0];for(int i=1;i<nums.size();i++){ans^=nums[i];}return ans;}