【LeetCode】Fizz Buzz解題レポート

【LeetCode】Fizz Buzz解題レポート
[LeetCode]
https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Total Accepted: 14302

Total Submissions: 24993

Difficulty: Easy

Question
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input: [4,3,2,7,8,2,3,1]
Output: [5,6]
Ways
最初は意外に効果的な方法で、暴力で解決するしかなかった.一つの方法だけでは問題に合わない余分な空間の要求がない.
方法1:

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        cList = list(range(1, len(nums) + 1))
        returnList = []
        for x in nums:
            cList[x - 1] = 0
        for x in cList:
            if x != 0:
                returnList.append(x)
        return returnList

AC:359 ms
方法2:
他の人を参考にして、私は1つの方法をマスターしました:その場でマイナスになってマークします.例えば[4,3,2,7,8,2,3,1]については,これらの要素をリストのインデックスとして指向する要素を負数に変換すると,負数に変換されていない位置は誰も指向していないため,この位置に対応する下付き文字は現れない.

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

AC:362 ms
この速度は依然として理想的ではない.
Date
2017年1月2日