每天进步一点点🤏

只出现一次的数字

  • 870 字

只出现一次的数字

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给你一个 非空 整数数组 nums,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1
输入：nums = [2,2,1]
输出：1

示例 2
输入：nums = [4,1,2,1,2]
输出：4

示例 3
输入：nums = [1]
输出：1

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
思路:
将数字作为key存入数组,值为出现的次数

代码:
function singleNumber($nums)
{
    $arr = [];

    foreach ($nums as $num) {
        if (!isset($arr[$num])) {
            $arr[$num] = 0;
        }
        $arr[$num]++;
    }

    foreach ($arr as $k => $val) {
        if ($val === 1) {
            return $k;
        }
    }

    return 0;
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
思路:
使用^异或运算,当a^a前后两个值相同时,返回0,因为只有一个值出现一次,其他的出现两次,刚好抵消为0

代码:
/**
 * @param Integer[] $nums
 * @return Integer
 */
function singleNumber($nums) {
    $a = 0;
    foreach ($nums as $num) {
        $a ^= $num;
    }

    return $a;
}