[LeetCode] 136. Single Number 单独数
LeetCode number single 单独 136
2023-09-27 14:28:37 时间
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1] Output: 1
Example 2:
Input: [4,1,2,1,2] Output: 4
由于要求时间复杂度O(n),空间复杂度O(1),所以不能用排序法,也不能使用map。
解法1:用两倍所有非重复元素和减去原数组。
解法2:位操作Bit Operation,使用二进制数位操作中的异或,同为0,异为1。主要考察位操作。
异或运算{\displaystyle A\oplus B}的真值表如下: F表示false,T表示true
A | B | ⊕ |
---|---|---|
F | F | F |
F | T | T |
T | F | T |
T | T | F |
Java:
public class Solution { public int singleNumber(int[] nums) { int res = 0; for (int num : nums) res ^= num; return res; } }
Python:
def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ return 2 * sum(set(nums)) - sum(nums)
Python:
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ res = 0 for num in nums: res ^= num return res
Python:
import operator from functools import reduce class Solution: """ :type nums: List[int] :rtype: int """ def singleNumber(self, A): return reduce(operator.xor, A)
C++:
class Solution { public: int singleNumber(vector<int>& nums) { int res = 0; for (auto num : nums) res ^= num; return res; } };
类似题目:
[LeetCode] 137. Single Number II 单独数 II
[LeetCode] 260. Single Number III 单独数 III
All LeetCode Questions List 题目汇总
相关文章
- Leetcode: Number of Boomerangs
- Leetcode: Sum of Two Integers && Summary: Bit Manipulation
- Leetcode: Strobogrammatic Number III
- Leetcode: Strobogrammatic Number
- Leetcode: Number of Digit One
- Leetcode: Combination Sum III
- Leetcode: Single Number
- [leetcode 44] Wildcard Matching
- leetcode 2 Add Two Numbers
- 【Leetcode】305.岛屿数量II(困难)
- 81、【栈与队列】leetcode ——232. 用栈实现队列(C++版本)
- 【LeetCode】Largest Number
- 【LeetCode】136. Single Number (4 solutions)
- [LeetCode] 1290. Convert Binary Number in a Linked List to Integer 二进制链表转整数
- [LeetCode] 1201. Ugly Number III 丑陋数之三
- [LeetCode] 1074. Number of Submatrices That Sum to Target 元素和为目标值的子矩阵数量
- [LeetCode] 1073. Adding Two Negabinary Numbers 负二进制数相加
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 1155. Number of Dice Rolls With Target Sum 掷骰子的N种方法
- [LeetCode] Number of Subarrays with Bounded Maximum 有界限最大值的子数组数量
- [LeetCode] Convert a Number to Hexadecimal 数字转为十六进制
- [LeetCode] 355. Design Twitter 设计推特
- [LeetCode] 260. Single Number III 单独的数字之三
- [LeetCode] Single Number 单独的数字
- leetcode 191. Number of 1 Bits 位1的个数(简单)
- leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球(中等)