第三十一天 Find All Numbers Disappear

因为一些事情，间断了几天，既然已经过去，就不再纠结
该坚持的，再继续坚持下去

过往不究，今天是否比昨天更长进了一点呢？
嗯看了这一季的《奇葩说》，那个“今天的你是否比昨天更博学了呢”的梗，目前看我还是蛮受用的，我经受了一个刺激，也需要改变一些

好，不再鸡汤了

今天的题目，其实并不难：

https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/description/

找到数组中没有出现的元素，数组是有范围的[1,n]。

要求不开额外的空间，时间复杂度为O(n)。

嗯，对于数组的题目，有一种“天然”的敏感度，就是希望先排个序，然后比较一下前后两个数字是否相等或是相差为1，如果不是，就补一下中间的数字，最后再分别补前后的数字

但只要是排序，就一定不是O(n)了，本着要先把事情做下去的思路，那么就写出了这样一个可以AC的答案：

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < 1:
            return []
        ret = []
        nums = sorted(nums)
        for index in range(0,len(nums)-1):
            if nums[index] == nums[index+1] or nums[index]+1 == nums[index+1]:
                continue
            else:
                for i in range(nums[index]+1,nums[index+1]):
                    ret.append(i)
        for i in range(1,nums[0]):
            ret.append(i)
        for i in range(nums[-1]+1,len(nums)+1):
            ret.append(i)
        return ret

那么是否可以有更好的方法呢？其实是有的，就是可以利用数组索引呢

因为数组的最大值的范围其实就是数组的长度，那么就可以先遍历一遍数组，把对应的位置的值都设置为负数
接着就是从1遍历到n，然后看下对应在数组中的值如果是负数的话，那么就证明出现过，否则就需要返回。

这里因为索引是从0开始，但数组的值是从1开始，要注意一下换算。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret = []
        for i in range(len(nums)):
            index = abs(nums[i])-1
            nums[index] = -abs(nums[index])
        for i in range(len(nums)):
            if nums[i] > 0:
                ret.append(i+1)
        return ret

这里还要特别注意一下，就是计算索引值的时候，需要取绝对值，因为如果有两个数字如果是相同的话，那么他们的索引值肯定也是一样的，接着设置的时候，前一个设置为负数的话，第二次就又设置为正数了。
而这个数值其实就是我们计算的索引值，那么这里两次就都需要取绝对值，算是一个小坑吧