使用Array.FindIndex时触发IndexOutOfRangeException的问题咨询

题目要求 #

给定一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须实现线性时间复杂度的解决方案，且仅使用常量额外空间。

你的代码 #

public class Solution
{
    public int SingleNumber(int[] nums)
    {
        int[] nums2 = new int[nums.Length];

        if (nums.Length == 1)
        {
            return nums[0];
        }

        for (int i = 0; i < nums.Length; i++)
        {
            if (!nums2.Contains(nums[i]))
            {
                nums2[i] = nums[i];
            }
            else
            {
                var x = Array.IndexOf(nums2, nums[i]);
                nums[x] = 0;
                nums[i] = 0;
            }
        }

        var index = Array.FindIndex(nums, value => value != 0);
        return nums[index];
    }
}

错误原因分析 #

你遇到的IndexOutOfRangeException确实是因为Array.FindIndex返回了-1，但问题根源不是题目条件不成立，而是你的代码逻辑错误地把唯一的目标元素也改成了0，导致数组中全是0，找不到非0值。

举个具体场景示例：
比如测试用例[0, 0, 1]：

1. 初始化nums2为全0数组。
2. i=0时，nums2.Contains(0)为true，进入else分支，找到x=0，将nums[0]和nums[0]（i=0）都设为0。
3. i=1时，nums[i]是0，nums2.Contains(0)为true，找到x=0，将nums[0]和nums[1]都设为0。
4. i=2时，nums[i]是1，nums2.Contains(1)为false，将nums2[2]设为1，但此时nums数组已经全是0了。
5. 最后Array.FindIndex找不到非0元素，返回-1，访问nums[-1]触发索引越界。

除此之外，你的代码还存在两个不符合题目要求的问题：

• 时间复杂度：nums2.Contains和Array.IndexOf都是O(n)操作，外层循环O(n)，整体是O(n²)，不满足线性时间要求。
• 空间复杂度：使用了nums2数组，空间复杂度O(n)，不符合常量额外空间要求。

正确解法（满足线性时间+常量空间） #

利用异或运算的特性可以完美解决这个问题：

• 任何数与0异或结果为自身：a ^ 0 = a
• 任何数与自身异或结果为0：a ^ a = 0
• 异或满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

遍历数组，将所有元素依次异或，最终结果就是唯一出现一次的元素：

public class Solution
{
    public int SingleNumber(int[] nums)
    {
        int result = 0;
        foreach (int num in nums)
        {
            result ^= num;
        }
        return result;
    }
}

这个解法的时间复杂度为O(n)，空间复杂度为O(1)，完全符合题目要求。

内容的提问来源于stack exchange，提问作者ByGoalZ