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 题解
双循环暴力法
// 方法一：双循环暴力法
// 两层循环遍历数组，发现相同元素跳出循环，假如索引是末尾了还没跳出说明是唯一元素。
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;
}
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
