136. 只出现一次的数字

Posted on | In
Words count in article: 219 | Reading time ≈ 1

题目

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

示例1：

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

示例2：

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

解法

解法一：

使用异或的特性。
任何数和自身异或为0，任何数和0异或，为其本身。

Java

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
    int result = nums[0];
    for (int i = 1;i < nums.length;i++) {
        result ^= nums[i];
    }
    return result;
}

解法二：

优化空间复杂度

不使用变量result，直接使用数组的第一个元素

Java

1
2
3
4
5
6
public int singleNumber(int[] nums) {
    for (int i = 1;i < nums.length;i++) {
        nums[0] ^= nums[i];
    }
    return nums[0];
}
0%