LeetCode-136. Single Number

发布于 2017-07-12 15:54:20

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?



这个题目跟第一个题目two sum一样,也是接受O(N),中间错了很多次,包括缩进等的错误,用国list.count但是List.count貌似也是自己循环一遍的。这个其实想起来也不复杂,先用sort,对list进行排序,比如[1,0,1],变成了[0,1,1],再用for以range(0,len(nums),2)循环,比较num[i]与num[i+1]是不是相等,如果不相等,说明第i个数就是要找对那个单数。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) > 1:
            nums.sort()
            for i in range(0,len(nums),2):
                try:
                    if nums[i]==nums[i+1]:
                        continue
                    else:
                        return nums[i]
                except IndexError:
                    return nums[i]
        else:
            return nums[0]