สมมติว่ามีรายการตัวเลขชื่อ nums ขนาด n ที่ทุกตัวเลขอยู่ในช่วง [1, n] บางตัวอาจปรากฏสองครั้ง ส่วนอื่นหนึ่งครั้ง เราต้องหาตัวเลขทั้งหมดใน [1, n] ที่ไม่อยู่ในรายการ คืนค่าเรียงเพิ่มขึ้น พยายามหาวิธีที่ใช้เวลาเชิงเส้นและพื้นที่คงที่
เช่น ถ้าอินพุตคือ [4, 4, 2, 2, 6, 6] ผลลัพธ์จะเป็น [1, 3, 5]
ขั้นตอนการแก้ปัญหา
- arr := อาร์เรย์ขนาด nums + 1 เติม 0
- สำหรับแต่ละ i ใน nums arr[i] := arr[i] + 1
- missing := รายการใหม่
- for i ในช่วง 0 ถึงขนาดของ arr ถ้า arr[i] == 0 และ i != 0 ใส่ i เข้า missing
- คืนค่า missing
ตัวอย่างโค้ด
class Solution:
def solve(self, nums):
arr = [0] * (len(nums) + 1)
for i in nums:
arr[i] += 1
missing = []
for i in range(len(arr)):
if arr[i] == 0 and i != 0:
missing.append(i)
return missing
ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))
อินพุต
[4, 4, 2, 2, 6, 6]
เอาต์พุต
[1, 3, 5]
