ครั้งแรกที่ขาดหายไปในเชิงบวกใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่ไม่ได้เรียงลำดับหนึ่งรายการ เราต้องหาจำนวนบวกที่ขาดหายไปน้อยที่สุด ดังนั้นหากอาร์เรย์เป็นแบบ [4, -3, 1, -1] ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตั้งค่า i :=0 และอัปเดต array nums โดยการเพิ่ม 0 ก่อนตัวเลขทั้งหมด

• สำหรับฉันอยู่ในช่วง 0 ถึงความยาวของ nums

  • ในขณะที่ nums[i]>=0 และ nums[i] <ความยาวของ nums และ nums[nums[i]] คือ notnums[i] −

    • nums[nums[i]] :=nums[i]

    • nums[i] :=nums[nums[i]]

• num :=1

• สำหรับฉันอยู่ในช่วง 1 ถึงความยาวของ nums

  • ถ้า num =nums[i] ให้เพิ่ม num ขึ้น 1

• ส่งคืนหมายเลข

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution(object):
   def firstMissingPositive(self, nums):
   i = 0
   nums = [0] + nums
   for i in range(len(nums)):
      while nums[i]>=0 and nums[i]<len(nums) and nums[nums[i]]!=nums[i]:
         nums[nums[i]],nums[i] = nums[i],nums[nums[i]]
      num = 1
      for i in range(1,len(nums)):
         if num == nums[i]:
            num+=1
      return num

ob = Solution()
print(ob.firstMissingPositive([4,-3,1,-1]))

อินพุต

[4,-3,1,-1]

ผลลัพธ์

2