每日一算 -- 只出现一次的数字

题目

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

说明:
你的算法应该是一个线性时间复杂度,你可以不用额外空间来实现它吗?

示例

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

示例

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

日常找规律

假如没有说明里面的要求,瞬间想到的解法可能就是:

  • 先排序再根据除了某个元素只出现一次以外,其余每个元素均出现两次这个题目条件,比较arr[i] !== arr[i+1]是否相等
  • 有的同学可能想到了利用对象进行存储出现的次数,很棒
  • 另一个就是不容易想到的就是^异或运算,^ 相同为假,不同为真

    实现方式

    排序实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function singleNumber(arr) {
    arr.sort()
    const len = arr.length
    for (let i = 0; i < len ; i = i + 2) {
    if (i + 1 >= len ) {
    return arr[i];
    }
    if (arr[i] != arr[i + 1]) {
    return arr[i];
    }
    }
    return -1
    }

hashMap存储数值出现的次数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function singleNumber(arr){
const sum = {}
for (let i = 0; i < arr.length; i++) {
if (!sum[arr[i]]) {
sum[arr[i]] = 0
}
sum[arr[i]]++
}
const newVal = Object.keys(sum)
for (let i = 0; i < newVal.length; i++) {
if (sum[newVal[i]] === 1) {
return newVal[i]
}
}
return -1
}

巧妙利用异或运算符,当两个值相同异或结果为0

1
2
3
4
5
6
function singleNumber(arr){
for (let i = 1; i < arr.length; i++) {
arr[0] ^= arr[i]
}
return arr[0]
}

总结