LeetCode——single-number(出现一次的数)

本文首发于github

题目描述

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

给定一个数组，除了某一个元素之外的其他元素都出现了两次，找出那个只出现了一次的数。

注意：你的算法应该在线性事件复杂度内完成，不应该使用额外空间。

解题思路

使用异或操作，由于异或操作有"相同得0，不同得1"的特性，所以讲所有元素顺序异或完之后结果即为那个只出现了一次的数。

代码

public int singleNumber(int[] A) {


        int res = A[0];
        for (int index = 1; index < A.length; index  ) {
            res = res ^ A[index];
        }
        return res;
    }

完整代码