:-: 15.1 只出现一次的数字 * * * * * **题干：** 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明：你的算法应该具有线性时间复杂度(如果一个算法的时间复杂度为O(n)，则称这个算法具有线性时间，或O(n)时间)。 你可以不使用额外空间来实现吗？ 示例 1: ~~~ 输入: [2,2,1] 输出: 1 ~~~ 示例 2: ~~~ 输入: [4,1,2,1,2] 输出: 4 ~~~ **题目分析：** 对位运算符不熟悉的，肯定要优先考虑最简单的暴力破解了，熟悉的肯定使用位运算符^,它的特性是a ^ a = 0; a ^ c ^ b ^ a = c ^ b。 **新手有可能遇到的解题思路陷阱：** 没有想到^位运算符呗。 **解题思路分析以及代码实现：** 第一种思路：直接暴力破解(不符合要求)。 第一种思路代码： ~~~ public static int singleNumber(int[] nums) { for (int i = 0; i < nums.length; i++) { int num = 0; for (int j = 0; j < nums.length; j++) { if (nums[i] == nums[j]) { num++; } } if (num == 1) { return nums[i]; } } return 0; } ~~~ **复杂度分析：** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第二种思路：先排序再暴力破解。 第二种思路代码： ~~~ public static int singleNumber(int[] nums) { if (nums.length == 1) { return nums[0]; } Arrays.sort(nums); if (nums[0] != nums[1]) { return nums[0]; } if (nums[nums.length - 1] != nums[nums.length - 2]) { return nums[nums.length - 1]; } for (int i = 2; i < nums.length - 2; i++) { if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) { return nums[i]; } } return 0; } ~~~ **复杂度分析：** 用到了Arrays.sort();，无法分析。具体情况可看源码。不想看源码等，这里提供两个博客链接（感谢两个博客的作者），仅作参考。 [Collections.sort()和Arrays.sort()排序算法选择](https://blog.csdn.net/TimHeath/article/details/68930482) [Java中Arrays.sort排序源码分析](https://blog.csdn.net/L_kanglin/article/details/72629926) 第三种思路：位运算符 第三种思路代码： ~~~ public static int singleNumber(int[] nums) { int rst = 0; for (int aA : nums) { rst ^= aA; System.out.println(rst); } return rst; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**