[Leetcode]Single Number

淩亂°似流年 2022-06-09 03:06 196阅读 0赞

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?  
整数型数组中，每个元素均出现两次，除了一个元素例外，如何找出这个元素？能否设计一个线性时间的算法，且不需要额外的存储空间？

# 解题思路 #

## （1）O（n^2）的解法 ##

*  对元素的出现次数进行统计，可进行n\*n循环，判断元素是否只出现了一次。这样时间复杂度为O(n^2), 不需要额外空间
 *  先对元素进行排序，然后进行相邻两元素的对比，如a1和a2对比，a3和a4对比，如果不同，则前一个元素(a1、a3)就是所要查找的元素。  
    给出第二种想法的代码

class Solution:
        # @param A, a list of integer
        # @return an integer
        def singleNumber(self, A):
            A.sort()
            for i in range(1, len(A), 2):
                if A[i] != A[i-1]: # 与前一元素对比
                    return A[i-1]
            return A[-1] # 要找的元素是最后一个元素

实现上主要就是相邻两元素的对比，循环间隔为2，与前一元素对比，如果不同，则返回前一元素。  
如果循环执行完没有返回，则返回列表中最后一个元素，如\[1, 1, 2, 2, 3\]，执行的循环为(1, 3)，在循环中最后一个元素不会参与对比（奇数个元素）

## （2）O（n）的解法 ##

发现了一个很有意思的解决方式：利用XOR运算，就是异或  
因为A XOR A = 0，且XOR运算是可交换的，于是，对于实例\{2,1,4,5,2,4,1\}就会有这样的结果：

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

就把只出现了一次的元素(其余元素均出现两次)给找出来了！

算法复杂度为O(n)，且不需要额外空间，代码如下：

class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            result = 0
            for i in nums:
                result^=i
            return(result)