目录
描述
方法一: 列表操作
思路
Java 实现
Python 实现
方法二: 哈希表
思路
Java 实现
Python 实现
方法三: 数学运算
思路
Java 实现
Python 实现
方法四: 位运算
思路
Java 实现
Python 实现
描述
给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素.
说明:
你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗?
示例 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\) 只出现一次, 其余的元素都出现两次. 对该数组中的所有元素进行异或运算可得,
- \[ \begin{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_x \end{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
复杂度分析同上.
来源: https://www.cnblogs.com/xugenpeng/p/9828673.html