home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

First Missing Positive ใน Python

กำหนดอาร์เรย์จำนวนเต็ม unsorted ต้องหาจำนวนเต็มบวกที่ขาดหายไปน้อยที่สุด

ตัวอย่าง: [4, -3, 1, -1] → 2

ขั้นตอนการแก้ปัญหา (Cyclic Sort)

  • เพิ่ม 0 เข้าหน้าอาร์เรย์ (เพื่อให้ index ตรงกับค่า)
  • วน i: while nums[i] ในช่วง [0, n) และ nums[nums[i]] != nums[i] → swap nums[i] กับ nums[nums[i]]
  • หลังจัดเรียงแล้ว วนหา num เริ่มจาก 1 ถ้า num == nums[i] → num++
  • คืนค่า num

ตัวอย่างโค้ด

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