สมมติว่าเรามีรายการองค์ประกอบที่เรียกว่า nums ขนาด n + 1 ซึ่งถูกเลือกจากช่วง 1, 2, ..., n อย่างที่เราทราบกันดีอยู่แล้วว่าโดยหลักการของหลุมพรางนั้นจะต้องมีการซ้ำซ้อน เราต้องหาที่ซ้ำกัน เป้าหมายของเราคือค้นหาภารกิจในเวลา O(n) และพื้นที่คงที่
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2,1,4,3,5,4] ผลลัพธ์จะเป็น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
q :=ผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ใน nums
-
n :=ขนาดของ nums
-
v :=ชั้นของ ((n - 1)*(n)/2)
-
ส่งคืน q - v
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(nums): q = sum(nums) n = len(nums) v = (n - 1) * (n) // 2 return q - v nums = [2,1,4,3,5,4] print(solve(nums))
อินพุต
[2,1,4,3,5,4]
ผลลัพธ์
4
