LeetCode第136题 只出现一次的数字
1. 题目描述
题目来源；LeetCode
链接：136. 只出现一次的数字
给你一个 非空 整数数组 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
除了某个元素只出现一次以外，其余每个元素均出现两次。
2. 解题方法
2.1 解法一（暴力求解）
使用循环遍历数组，两个两个元素进行比较，用计数器来记录数组中的元素个数，如果两个元素相等，则计数器加一，如果不相等则不加一，一遍比较之后，判断计数器是否为1，除和自己相等没有其他元素相等的情况，这就是我们要找的值，直接返回即可
#include <stdio.h>
int singleNumber(int* nums, int numsSize)
{
int i = 0;
for (i = 0; i < numsSize; i++)
{
int j = 0;
int count = 0; //计数器
for (j = 0; j < numsSize; j++)
{
if (nums[i] == nums[j])
{
count++; //当数组中有相同的两个元素则计数器加1
}
}
if (count == 1)
{
return nums[i];
}
}
return 0;
}
int main()
{
int arr[] = {
2,5,3,2,10,5,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = singleNumber(arr, sz);
printf("single number is %d\n", ret);
}
代码运行结果:>
single number is 10
2.2 解法二（排序后判断）
先使用C语言中的库函数，qsort排序下数组，然后遍历数组，当两个相邻的元素的不相同时，则说明找到了唯一的元素
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* p1, const void* p2)
{
return *(int*)p1 - *(int*)p2;
}
int singleNumber(int* nums, int numsSize)
{
qsort(nums, numsSize, sizeof(int), cmp); //qsort排序数组
int i = 0;
int target = nums[0];
for (i = 1; i < numsSize; i++)
{
if (target != nums[i]) //1 2两个元素比较 3 4比较 ....
{
break; //当两个元素不相等时说明找到了，则退出循环
}
i++; //i++，循环进来时，nums下标为奇数
target = nums[i]; //将偶数下标的元素赋值给target
}
return target;
}
int main()
{
int arr[] = {
2,5,3,2,10,5,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = singleNumber(arr, sz);
printf("single number is %d\n", ret);
}
代码运行结果:>
single number is 10
2.3 解法三（异或）
两个相同的数相异或为0，0和非零0数相异或，等于那个非0数
#include <stdio.h>
int singleNumber(int* nums, int numsSize)
{
int ret = 0;
int i = 0;
for (i = 0; i < numsSize; i++)
{
ret ^= nums[i];
}
return ret;
}
int main()
{
int arr[] = {
10,2,5,3,2,5,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = singleNumber(arr, sz);
printf("single number is %d\n", ret);
}
代码运行结果:>
single number is 10
