ChunNote
0%

leetCode-136:Single Number

发表于 分类于

问题描述

给定一个非空整数数组，数组中的元素要么出现两次，要么只出现一次。要求在 O(n) 的时间复杂度和 O(1) 的空间复杂度内将数组中只出现一次的数字找到并返回。题目链接：**点我**

样例输入输出

输入：[1,2,3,4,2,3,1]

输出：4

输入：[1]

输出：1

问题解法

此题如果去除时间复杂度和空间复杂度的限制，会有多种解法，其中一种直观的方法是使用 map 存储每个数字出现的次数，然后将出现一次的数字返回。但这不满足题目对空间复杂度的要求。要想在 O(n) 的时间复杂度和 O(1) 的空间复杂度内解答此题，可以利用异或运算的特点，将数组中所有元素进行异或，最终剩下的数字就是只出现一次的数字（出现两次的数字异或后为 0）， 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
    public int singleNumber(int[] nums)
    {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++)
        {
            result ^= nums[i];
        }
        
        return result;
    }
}