Voyz's Studio.

LeetCode算法笔记--只出现一次的数字

字数统计: 297阅读时长: 1 min
2021/01/01 Share

LeetCode算法笔记-Day55

136. Single Number

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?

1
2
3
4
5
6
7
example:

Input: [2,2,1]
Output: 1

Input: [4,1,2,1,2]
Output: 4

方法一:傻瓜算法

Analyse:

如果没有时间复杂度和空间复杂度的限制,这道题有很多种解法。  

Answer:

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
for(let i=0;i<nums.length;i++){
if(nums.indexOf(nums[i]) == nums.lastIndexOf(nums[i])){
return nums[i];
}
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二 位运算

Analyse:

可使用异或运算。异或运算有以下三个性质:

  • a⊕0 = a
  • a⊕a = 0
  • a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b

假设数组中有 2m+1 个数,其中有 m 个数各出现两次,一个数出现一次。数组中的全部元素的异或运算结果总是可以写成如下形式:
公式1
化简后:
公式2

Answer:

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let res = 0;
for(let i=0;i<nums.length;i++){
res ^= nums[i]
}
return res;
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
CATALOG
  1. 1. LeetCode算法笔记-Day55
    1. 1.1. 136. Single Number
    2. 1.2. 方法一:傻瓜算法
      1. 1.2.1. Analyse:
      2. 1.2.2. Answer:
    3. 1.3. 方法二 位运算
      1. 1.3.1. Analyse:
      2. 1.3.2. Answer: