一、题目描述与要求
136. 只出现一次的数字 - 力扣（LeetCode）
题目描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例
示例1：
输入：nums = [2,2,1]
输出：1
示例2：
输入：nums = [4,1,2,1,2]
输出：4
示例3：
输入：nums = [1]
输出：1提示
- 1 <= nums.length <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
- 除了某个元素只出现一次以外，其余每个元素均出现两次。
二、解题思路
总的思路：
首先分析题目，题目要求是找出数组中只出现了一次的数字，因此我们需要思考怎么找出这一个数字。且题目要求了只能使用常量额外空间，也就是说不能利用数组等多个空间的变量来解决问题。同时时间复杂度也要是线性的。
最简单的方法就是统计每个数字出现的次数（题目规定了其他数字只出现两次），将数组中的数字与除它以外数组的每一个元素进行比较，相同则次数增加，遍历比较完后判断次数是否为1，如果为1则将这一数字赋值给result。重复以上步骤直至遍历完整个数组。【最朴素的实现方法，但是会超时。时间复杂度O（n²）空间复杂度为O（1）】
另一个方法则是需要利用位运算中的异或运算来找出只出现了一次的数字。a⊕0=a。a⊕a=0。a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。因此可以将数组第一个值赋值给result，然后将result与数组中的元素以此进行异或运算，最后就能得到目标数字。【需要对位运算性质熟悉】
具体步骤：
嵌套循环遍历方法：
①定义辅助变量result与count，result初值随便定义，count在第一层for循环中定义初值为1
②for循环嵌套for循环，将数组中的数字与除它以外数组的每一个元素进行比较，判断次数是否为1，如果为1则将这一数字赋值给result。
③返回result文章来源地址https://www.toymoban.com/news/detail-532778.html
异或运算方法：
①定义辅助变量result=nums[0]
②利用for循环遍历数组，将result与数组的每个元素进行异或运算并保存结果文章来源：https://www.toymoban.com/news/detail-532778.html
③返回result
三、具体代码【C语言】
①嵌套循环遍历方法：【时间O(n²) 空间O(1) 】leetcode提交超时
int singleNumber(int* nums, int numsSize) {
if (numsSize == 1) return nums[0];//如果数组只有一位的话则直接输出
int result = 0;
int count;
//遍历整个数组，统计出现次数
for (int i = 0; i < numsSize; i++) {
count = 1;
for (int j = 0; j < numsSize; j++) {
if (j != i) {
if (nums[i] == nums[j]) {
++count;//有重复的，次数+1
}
}
}
if (count == 1)//只出现一次
{
result = nums[i];
}
}
return result;
}②异或运算方法：【时间O(n) 空间O(1) 】
int singleNumber(int* nums, int numsSize){
if (numsSize == 1) return nums[0];//如果数组只有一位的话则直接输出
int result = nums[0];
//遍历整个数组
for (int i = 1; i < numsSize; i++) {
result^=nums[i];
}
return result;
}到了这里，关于2023年7月3日leetcode每日一题打卡——136.只出现一次的数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
