leetcode做题笔记136. 只出现一次的数字

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

思路一：快排（时间复杂度不符）

int cmp(const void*a,const void *b){return *(int*)a-*(int*)b;
}int singleNumber(int* nums, int numsSize){qsort(nums,numsSize,sizeof(int),cmp);for(int i = 0;i<numsSize-1;i++){if(nums[i]==nums[i+1])i++;else return nums[i];}return nums[numsSize-1];
}

分析：

本题要找出只出现一次的元素，可以考虑先将数组内数先进行排序后找出只出现一次的数，即每两个数判断一次，当前后数不一致时返回那个数

思路二：位运算

int singleNumber(int* nums, int numsSize)
{int n = nums[0];int i = 0;for(i = 1;i < numsSize;i ++){n = n ^ nums[i];}return n;
}

分析：

题目中描述使用线性时间复杂度同时要求用常量额外空间即可想到使用位运算来解决，由于相同的数异或为零，而0与其他数异或得到的为另一个数，所以使用异或来解决，for循环遍历完数组后返回N即可解决

总结：

本题考察位运算的用法，在数据量不大的情况下，快排所用时间不一定多于位运算，了解位运算的几个公式即可解决