136.只出现一次的数字
136.1 题目
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1：
输入：nums = [2,2,1]
输出：1
示例 2：
输入：nums = [4,1,2,1,2]
输出：4
示例 3：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- 除了某个元素只出现一次以外，其余每个元素均出现两次。
136.2 题解
方法一：双循环暴力法
思路
最朴素的想法：对于每个元素，检查数组中是否还有另一个相同的元素。如果遍历完都没找到，那它就是唯一的那个。
这个方法虽然直观，但时间复杂度 O(n²)，对于 3×10⁴ 的数据规模会超时。
举个例子：nums = [4,1,2,1,2]
- 检查4：没有另一个4，返回4
复杂度分析
- 时间复杂度：
O(n²)，两层循环 - 空间复杂度：
O(1)，只使用常数变量
代码
// 方法一：双循环暴力法
// 两层循环遍历数组，发现相同元素跳出循环，假如索引是末尾了还没跳出说明是唯一元素。
static int SingleNumber1(int[] nums)
{
int j; // 用于保存内层循环的索引值
// 外层循环遍历数组中的每个元素
for (int i = 0; i < nums.Length; i++)
{
// 内层循环遍历数组中的每个元素，查找与外层循环元素相等且索引不同的元素
for (j = 0; j < nums.Length; j++)
{
// 如果找到相等且索引不同的元素，跳出内层循环
if (nums[i] == nums[j] && i != j)
{
break;
}
}
// 如果内层循环完成而没有找到相等且索引不同的元素，说明外层循环元素是唯一出现一次的元素
if (j == nums.Length)
{
return nums[i]; // 返回找到的唯一元素
}
}
// 如果整个数组都被遍历，仍未找到唯一元素，则返回-1表示未找到
return -1;
}
方法二：集合容器辅助
思路
用一个集合来辅助：遍历数组，如果当前元素不在集合中就添加，如果已经在集合中就移除。最后集合里剩下的就是只出现一次的元素。
原理：出现两次的元素会先添加后移除，只有出现一次的元素会留在集合中。
举个例子：nums = [4,1,2,1,2]
- 4：不在集合，添加 → {4}
- 1：不在集合，添加 → {4,1}
- 2：不在集合，添加 → {4,1,2}
- 1：在集合，移除 → {4,2}
- 2：在集合，移除 → {4}
- 结果：4
注意：用 List 的话 Contains 和 Remove 都是 O(n)，总复杂度还是 O(n²)。用 HashSet 可以优化到 O(n)。
复杂度分析
- 时间复杂度：
O(n²)（List）或O(n)（HashSet） - 空间复杂度：
O(n)，存储集合
代码
// 方法二：集合容器辅助
// 使用List集合，发现list中没有当前元素添加到list，再次发现移除，最后剩下的就是单个元素
// 也可以使用Dictionary统计元素出现次数
static int SingleNumber2(int[] nums)
{
List<int> list = new List<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!list.Contains(nums[i]))
{
list.Add(nums[i]);
}
else
{
list.Remove(nums[i]);
}
}
return list[0];
}
方法三：位运算异或
利用异或运算的性质：a ^ a = 0，a ^ 0 = a。由于除一个元素外其他元素都出现两次，对数组所有元素进行异或操作，出现两次的元素会相互抵消，最终结果就是只出现一次的元素。
复杂度分析：
- 时间复杂度：
O(n)，只需遍历一次数组。 - 空间复杂度：
O(1)，只使用常数额外变量。
// 方法三：位运算异或
// 两次异或能让元素变成本身
// 使用位运算异或操作，对数组中的所有元素进行异或操作，最终结果即为只出现一次的元素
static int SingleNumber3(int[] nums)
{
int result = 0;
// 对数组中的所有元素进行异或操作
foreach (int num in nums)
{
result ^= num;
}
// 最终结果即为只出现一次的元素
return result;
}
136.3 代码
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
#region 题目
// 给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
// 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
// 示例 1：
// 输入：nums = [2,2,1]
// 输出：1
// 示例 2：
// 输入：nums = [4,1,2,1,2]
// 输出：4
// 示例 3：
// 输入：nums = [1]
// 输出：1
#endregion
#region 测试
// 示例 1
int[] nums1 = { 2, 2, 1 };
int result1 = SingleNumber1(nums1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
int result1_2 = SingleNumber2(nums1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
int result1_3 = SingleNumber3(nums1);
Console.WriteLine($"示例1 方法3 输出：{result1_3}");
// 示例 2
int[] nums2 = { 4, 1, 2, 1, 2 };
int result2 = SingleNumber1(nums2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
int result2_2 = SingleNumber2(nums2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
int result2_3 = SingleNumber3(nums2);
Console.WriteLine($"示例2 方法3 输出：{result2_3}");
// 示例 3
int[] nums3 = { 1 };
int result3 = SingleNumber1(nums3);
Console.WriteLine($"示例3 方法1 输出：{result3}");
int result3_2 = SingleNumber2(nums3);
Console.WriteLine($"示例3 方法2 输出：{result3_2}");
int result3_3 = SingleNumber3(nums3);
Console.WriteLine($"示例3 方法3 输出：{result3_3}");
#endregion
}
#region 答案
// 方法一：双循环暴力法
// 两层循环遍历数组，发现相同元素跳出循环，假如索引是末尾了还没跳出说明是唯一元素。
static int SingleNumber1(int[] nums)
{
int j; // 用于保存内层循环的索引值
// 外层循环遍历数组中的每个元素
for (int i = 0; i < nums.Length; i++)
{
// 内层循环遍历数组中的每个元素，查找与外层循环元素相等且索引不同的元素
for (j = 0; j < nums.Length; j++)
{
// 如果找到相等且索引不同的元素，跳出内层循环
if (nums[i] == nums[j] && i != j)
{
break;
}
}
// 如果内层循环完成而没有找到相等且索引不同的元素，说明外层循环元素是唯一出现一次的元素
if (j == nums.Length)
{
return nums[i]; // 返回找到的唯一元素
}
}
// 如果整个数组都被遍历，仍未找到唯一元素，则返回-1表示未找到
return -1;
}
// 方法二：集合容器辅助
// 使用List集合，发现list中没有当前元素添加到list，再次发现移除，最后剩下的就是单个元素
// 也可以使用Dictionary统计元素出现次数
static int SingleNumber2(int[] nums)
{
List<int> list = new List<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!list.Contains(nums[i]))
{
list.Add(nums[i]);
}
else
{
list.Remove(nums[i]);
}
}
return list[0];
}
// 方法三：位运算异或
// 两次异或能让元素变成本身
// 使用位运算异或操作，对数组中的所有元素进行异或操作，最终结果即为只出现一次的元素
static int SingleNumber3(int[] nums)
{
int result = 0;
// 对数组中的所有元素进行异或操作
foreach (int num in nums)
{
result ^= num;
}
// 最终结果即为只出现一次的元素
return result;
}
#endregion
}
136.4 运行结果
示例1 方法1 输出：1
示例1 方法2 输出：1
示例1 方法3 输出：1
示例2 方法1 输出：4
示例2 方法2 输出：4
示例2 方法3 输出：4
示例3 方法1 输出：1
示例3 方法2 输出：1
示例3 方法3 输出：1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
