leecode第二天-使用异或找出数组中的非重复元素

leecode题目描述如下：

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

思路：

最开始想到的是使用排序，排序之后就很容易找到非重复元素了。

后面看到网上有更巧妙的解决办法，即使用异或来找出非重复元素，因为重复的元素经异或之后就互相抵消为0了，最后数组各个元素经过异或计算之后的结果就是那个唯一的非重复元素。

代码：

class Solution(object):

    def singleNumber(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        num = 0

        for i in nums:

            num = num ^ i

        return num

def stringToIntegerList(input):

    return json.loads(input)

def intToString(input):

    if input is None:

        input = 0

    return str(input)

def main():

    import sys

    def readlines():

        for line in sys.stdin:

            yield line.strip('\n')

    lines = readlines()

    while True:

        try:

            line = lines.next()

            nums = stringToIntegerList(line)

            ret = Solution().singleNumber(nums)

            out = intToString(ret)

            print out

        except StopIteration:

            break

if __name__ == '__main__':

    main()

巴特西

leecode第二天-使用异或找出数组中的非重复元素

最新文章

热门文章