First missing positive

Saralanmagan butun sonlar massivi nums berilgan. Unda ishtirok etmagan eng kichik musbat (1, 2, ...) butun sonni toping.

Siz yozgan algoritm O(n) vaqtda va iloji boricha doimiy O(1) xotira hajmi bilan ishlashi zarur.

func solve(nums []int) int {
    // ...
}

Misollar

Input: nums = [1,2,0]
Output: 3
Tushuntirish: 1 va 2 bor, demak eng kichik tushib qolgan son 3.

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

Input: nums = [7,8,9,11,12]
Output: 1

Maslahatlar

1. O(n) vaqt va O(1) qo'shimcha xotira bilan yechish uchun berilgan massivning o'zini xesh-jadval o'rnida ishlatishni o'ylab ko'ring — 1 dan n gacha bo'lgan har bir musbat son x uchun uning "to'g'ri" joyi x-1 indeksi hisoblanadi.
2. Massiv bo'ylab yurib, agar nums[i] 1 dan n oralig'ida bo'lsa va hali o'z to'g'ri joyida (nums[nums[i]-1]) turmagan bo'lsa, nums[i] bilan nums[nums[i]-1] ni almashtiring va shu tekshiruvni shu indeksda takrorlayvering. Shundan so'ng yana bir marta yurib, nums[i] != i+1 bo'lgan birinchi indeksni toping — javob i+1; agar barchasi joyida bo'lsa javob n+1.