Python3解leetcode Single Number

问题描述:

 

Given a non-empty 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?

 

Example 1:

 

Input: [2,2,1]
Output: 1

 

Example 2:

 

Input: [4,1,2,1,2]
Output: 4

 

思路:

考虑异或运算, 例如5^6,就是101^110,结果是011.即两个完全相同的数字进行异或运算,得到的结果为0,。

根据以上特性,将所有num中的数字依次进行异或运算,则其中重复的项经过运算为0,最终结果即单个的项

又由于尽量不适用其他内存,因而考虑将每一步异或结果放置于num[0]的位置

代码:

 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in nums[1:]:
            nums[0] = i^nums[0]
        return nums[0]

 

上一篇:【BZOJ】1415: [Noi2005]聪聪和可可【期望】【最短路】【记忆化搜索】


下一篇:Java设计模式之过滤器模式