สมมติว่าเรามีอาร์เรย์ที่เรียงลำดับของจำนวนบวก อาร์เรย์นี้เรียงลำดับจากน้อยไปมาก er ต้องหาค่าบวกที่น้อยที่สุดที่ไม่สามารถแสดงเป็นผลรวมขององค์ประกอบของชุดย่อยของที่กำหนด ชุด. เราต้องแก้ปัญหานี้ในเวลา O(n)
ดังนั้น หากอินพุตเป็น A =[1, 4, 8, 12, 13, 17] ผลลัพธ์จะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ A
-
ตอบ :=1
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
ถ้า A[i] <=ตอบ แล้ว
-
ตอบ :=ตอบ + A[i]
-
-
มิฉะนั้น
-
ออกจากวง
-
-
-
ส่งคืนคำตอบ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def get_smallest_element(A): n = len(A) answer = 1 for i in range (0, n ): if A[i] <= answer: answer = answer + A[i] else: break return answer A = [1, 4, 8, 12, 13, 17] print(get_smallest_element(A))
อินพุต
[1, 4, 8, 12, 13, 17]
ผลลัพธ์
2
