[Leetcode 136][Easy]-只出现一次的数字

目录

题目描述

具体思路

题目描述

原题链接

具体思路

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

//快慢指针+sort
    int 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;
    }