一. 简介
本文记录力扣网上编程题目，主要涉及数组方面的，以 C语言实现。
二. 力扣网C语言编程题：只出现一次的数字
题目： 只出现一次的数字
给你一个 非空 整数数组 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
除了某个元素只出现一次以外，其余每个元素均出现两次。
题目分析：
数组中有一个元素只出现一次，剩下的其他元素都是出现两次，这里查找出现一次的元素。
首先第一种比较笨的办法就是暴力解法。遍历数组元素，数组每个元素与其他元素进行比较，找到出现一次的元素。
其次可以考虑使用哈希表。哈希表有键key 和 value，可以将元素值作为key，出现次数作为 value,最后统计次数。
解题思路一：（暴力解法）
遍历数组元素，数组每个元素与其他元素进行比较，找到出现一次的元素。那么每个元素都要跟数组中所有元素比较一次，则需要双层循环实现。
时间负责度为O(n*n)，空间负责度为 O(1)；
C语言实现如下：
int singleNumber(int* nums, int numsSize) {
int i,j;
int data = 0;
for(i = 0; i < numsSize; i++) {
for(j = 0; j < numsSize; j++) {
if((nums[i] == nums[j]) && (i != j)) {
break;
}
if(j == numsSize-1) {
data = nums[i];
}
}
}
return data;
}可以看出，暴力解决方法的时间复杂度为O(n*n)，不满足要求。
解题思路二：（哈希表）
1. 遍历数组，求数组中最大值和最小值，创建哈希表数组；
2. 遍历哈希表数组，统一每个元素出现次数；
3. 遍历哈希表数组，查找出现一次的元素；
可以估算出该方法的时间复杂度为 O(n)，哈希表需要跟数组元素创建一个，则空间复杂度为O(n)；
C语言实现如下：
int singleNumber(int* nums, int numsSize) {
int i = 0;
int max = 0, min = 0;
for(i = 0; i < numsSize; i++) {
min = min > nums[i]? nums[i]:min;
max = max < nums[i]? nums[i]:max;
}
int n = max-min+1;
int hash_table[n];
memset(hash_table, 0, sizeof(hash_table));
for(i = 0; i < numsSize; i++) {
hash_table[nums[i]-min] += 1;
}
for(i = 0; i < numsSize; i++) {
if(hash_table[nums[i]-min] == 1) {
return nums[i];
}
}
return 0;
}哈希表解决方法的空间复杂度都不满足要求。
解题思路三：（位运算）
解题思路三考虑使用位运算，使用 "^"（异或）运算。
首先，了解下 "异或"运算的特点：
0 ^ 任何数 == 任何数 // 0和 任何数进行异或运算，结果是任何数
a ^ a == 0 //表示任何数和自己进行 异或运算都为0
//异或操作满足交换律和结合律
a ^ b ^ a == a ^ a ^ b == （a ^ a）^ b == b 那么，数组中只有一个数字出现了一次，剩下的元素都出现了两次，也就说，遍历数组元素一遍，那么所有元素进行一轮异或运算之后，最后得到的数字就是出现一次的元素（出现两次的元素经过异或运算之后就为0了，相互抵消了）；
C语言实现如下：
int singleNumber(int* nums, int numsSize) {
int i = 0;
int data = nums[0];
while(i < numsSize) {
data = data ^ nums[i];
i++;
}
return data;
}可以看出，位运算方法的时间复杂度为 O(n)，空间复杂度为 O(1)。满足了题目要求。