betway88必威
  咨询电话:13679632321

betway必威手机版

【LeetCode题解】136_只出现一次的数字

目录

【LeetCode题解】136_只出现一次的数字描述方法一:列表操作思路Java 实现Python 实现方法二:哈希表思路Java 实现Python 实现方法三:数学运算思路Java 实现Python 实现方法四:位运算思路Java 实现Python 实现

【LeetCode题解】136_只出现一次的数字

描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]输出: 1

示例 2:

输入: [4,1,2,1,2]输出: 4

方法一:列表操作

思路

新建一个变量(列表对象),遍历数组中的所有元素,如果元素在列表中存在,则删除该元素;如果元素在列表中不存在,则向列表中添加该元素。最后,列表中剩余的唯一元素就是我们找的唯一只出现一次的数字。

Java 实现

class Solution { public int singleNumber(int[] nums) { List<Integer> list = new LinkedList<>(); for (int num : nums) { if (list.contains(num)) { list.remove(new Integer(num)); } else { list.add(num); } } return list.get(0); }}

复杂度分析:

时间复杂度:(O(n^2))空间复杂度:(O(n))

Python 实现

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ l = list() for num in nums: if num in l: l.remove(num) else: l.append(num) return l.pop()# 超出时间限制

复杂度分析同上。

方法二:哈希表

思路

思路和方法一相同,只是存放数据的容器改用哈希表,由于哈希表查询操作的时间复杂度是 (O(1)) 的,因此,算法最终的时间复杂度降为 (O(n))

Java 实现

class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (map.containsKey(num)) { map.remove(num); } else { map.put(num, 1); } } return map.entrySet().iterator().next().getKey(); }}

复杂度分析:

时间复杂度:(O(n))空间复杂度:(O(n))

Python 实现

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ d = dict() for num in nums: try: d.pop(num) except: d[num] = 1 return d.popitem()[0]

复杂度分析同上。

方法三:数学运算

思路

由于数组中的数字除了唯一一个数字只出现一次外,其余都是出现两次的,因此,如果我们将所有的数字乘以 2 再减去数组中所有的元素,则可以得到只出现一次的数字,即[2 * (a_1 + a_2 + ldots + a_n + a_x) - (a_1 + a_1 + ldots + a_n + a_n + a_x) = a_x]其中,(a_1)(a_n) 是出现两次的数字,(a_x) 则是出现两次的数字。

Java 实现

class Solution { public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<>(); int arraySum = 0; for (int num : nums) { set.add(num); arraySum += num; } int doubleSum = 0; for (int num : set) { doubleSum += (2 * num); } return doubleSum - arraySum; }}

复杂度分析:

时间复杂度:(O(n))空间复杂度:(O(n))

Python 实现

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ return 2 * sum(set(nums)) - sum(nums)

复杂度分析同上。

方法四:位运算

思路

先来回顾一下两个位运算:

任何数与 0 异或都不改变它的值,即 (a oplus 0 = a)任何数与其自身异或都为 0,即 (a oplus a = 0)

假设题目中描述的数组为 ([a_1,, a_1,, a_2,, a_2,, ldots,, a_n,, a_n,, a_x]) ,其中,(a_x) 只出现一次,其余的元素都出现两次。对该数组中的所有元素进行异或运算可得,[egin{align*}& ,,a_1 oplus a_1 oplus ldots oplus a_n oplus a_n oplus a_x \= & ,,(a_1 oplus a_1) oplus ldots oplus (a_n oplus a_n) oplus a_x \= &,, 0 ,oplus ldots oplus 0 ,oplus a_x \= &,, a_xend{align*}]因此,只需要遍历数组中的所有元素,依次进行两两异或操作就可以找出只出现一次的元素。

Java 实现

class Solution { public int singleNumber(int[] nums) { int ret = nums[0]; for (int i = 1; i < nums.length; ++i) { ret ^= nums[i]; } return ret; }}

复杂度分析:

时间复杂度:(O(n))空间复杂度:(O(1))

Python 实现

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ ret = 0 for num in nums: ret ^= num return ret

复杂度分析同上。