- 个人博客：https://javaniuniu.com/
- 难度：
简单 - 本题涉及算法：
异或运算数组 - 思路：
异或运算组 - 类似题型：
- 1. 两数之和
- 136. 只出现一次的数字
- 169. 多数元素
- 面试题56 - I. 数组中数字出现的次数
题目 136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例
示例 1:
复制代码
1
2
3输入: [2,2,1] 输出: 1
示例 2:
复制代码
1
2
3输入: [4,1,2,1,2] 输出: 4
方法一 数组
解题思路
- 题目说 其余每个元素均出现两次，那么当元素第一次出现，则添加到数组，再次出现则删除该元素
- 除了某个元素只出现一次以外，那么剩下的最后一个元素 就是题解
复制代码
1
2
3
4
5
6
7
8
9def singleNumber(nums): no_duplicate_list = [] for num in nums: if num not in no_duplicate_list: no_duplicate_list.append(num) else: no_duplicate_list.remove(num) return no_duplicate_list.pop() # 在 数组中取出该数字
复杂度分析
- 时间复杂度度： O ( n ) O(n) O(n) 如果当前数组的长度为 n n n ，则每个元素遍历一遍，则为 n n n
- 空间复杂度度： O ( n / 2 + 1 ) O(n/2+1) O(n/2+1) ，如果当前数组 前 n / 2 + 1 n/2+1 n/2+1 个元素为不同元素，则最长需保存 n / 2 + 1 n/2+1 n/2+1 个元素
方法二 位运算
解题思路
- 交换律： p ⊕ q = q ⊕ p p⊕q=q⊕p p⊕q=q⊕p
- 结合律： p ⊕ ( q ⊕ r ) = ( p ⊕ q ) ⊕ r p⊕(q⊕r)=(p⊕q)⊕r p⊕(q⊕r)=(p⊕q)⊕r
- 恒等率： p ⊕ 0 = p p⊕0=p p⊕0=p
- 归零率： p ⊕ p = 0 p⊕p=0 p⊕p=0
代码
java
复制代码
1
2
3
4
5
6
7
8
9
10
11class Solution { public int singleNumber(int[] nums) { int sum = 0; for(int i=0;i<nums.length;i++) { sum ^= nums[i]; // 异或 } return sum; } }
python
复制代码
1
2
3
4
5
6
7
8
9
10
11
12class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ sum = 0 for num in nums: sum ^= num return sum
复杂度分析
- 时间复杂度度： O ( n ) O(n) O(n) 如果当前数组的长度为 n n n ，则每个元素遍历一遍，则为 n n n
- 空间复杂度度： O ( 1 ) O(1) O(1)
- 如果你觉得本文对你有帮助，请点赞????支持
- 如果有疑惑或者表达不到位的额地方 ，请在下面????评论区指出
最后
以上就是凶狠洋葱最近收集整理的关于[leetcode]136. 只出现一次的数字的全部内容，更多相关[leetcode]136.内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[leetcode]136. 只出现一次的数字](/uploads/reation/bcimg4.png)
发表评论 取消回复