Leetcode 448 Find All Numbers Disappeared in an Array

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Input: nums = [1, 3, 4, 3]
Output: [2]

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

• 1’den n’e kadar olan sayıları içeren bir set liste oluştururuz.
• Örneğin [1,4] için [1,2,3,4] oluşur.Daha sonra verilen listeyi dolaşırız.
• Listenin içerdiği her sayıyı elimizdeki set listeden çıkarırız.Kalan ilk listede bulunmayan sayı olur.

• Elimizdeki listeyi dolaşırız.Ve oradaki her değer için değer-1 indexi negatif yaparız.Daha sonra elimizdeki listeyi tekrar dolaştığımızda pozitif kalanların indexlerinin 1 fazlası listede olmayan değerleri verir.Yeni bir liste oluşturulmadığı için Space complexity : O(1).

 |
​[1, 3, 4, 3]	1-1 = 0 -> 0. indexi -yap
     |
​[-1, 3, 4, 3]	3-1 = 2 -> 2. indexi -yap
         |
​[-1, 3, -4, 3]	4-1 = 3 -> 3. indexi -yap
             |
​[-1, 3, -4, -3]3-1 = 2 -> 2. indexi -yap zaten -

​[-1, 3, -4, -3] pozitif olan  sadece 1. index 1+1 = 2 listedeki eksik sayı

def find_disappeared_numbers_in_array(nums):
    length_nums = len(nums)
    all_numbers_set = set(range(1, length_nums + 1))

    for num in nums:
        if num in all_numbers_set:
            all_numbers_set.remove(num)

    return list(all_numbers_set)

class Solution:
    def findDisappearedNumbers(self, nums):
        for i in range(len(nums)):            
            index = abs(nums[i]) - 1    # be aware to use absoluate value!!!  the ith element may be negative 
            if nums[index] > 0:
                nums[index] = -nums[index]
        anw = list()
        for i in range(len(nums)):
            if nums[i] > 0:
                anw.append(i+1)
        return anw