只出现一次的数字【LC136】
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
map
使用map统计每个数字出现的次数，最后返回只出现一次的元素
- 代码
class Solution { public int singleNumber(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0)+1); } Set<Map.Entry<Integer,Integer>> set = map.entrySet(); for (Map.Entry<Integer,Integer> node : set){ if (node.getValue() == 1){ return node.getKey(); } } return -1; } }
- 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
排序
将数组从小到大排序，返回与下一个元素不相等的元素
class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); int i = 0; while ( i < nums.length - 1 ){ if (nums[i] == nums[i+1]){ i = i + 2; }else{ return nums[i]; } } return nums[i]; } }
- 复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
*异或
任何一个数字异或它自己的结果都是0。如果将数组中的所有数字进行异或运算，那么最终的结果就是那个只出现一次的数字
- 代码
class Solution { public int singleNumber(int[] nums) { int res = 0; for (int i = 0; i < nums.length; i++){ res = res ^ nums[i]; } return res; } }
- 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
