โปรแกรมตรวจสอบทุกรายการย่อยในรายการที่มีองค์ประกอบที่ไม่ซ้ำกันอย่างน้อยหนึ่งรายการใน Python

สมมติว่าเรามีรายการองค์ประกอบที่เรียกว่า nums เราต้องตรวจสอบว่ารายการย่อยแต่ละรายการมีองค์ประกอบอย่างน้อย 1 รายการในนั้นซึ่งเกิดขึ้นเพียงครั้งเดียวในรายการย่อยหรือไม่ เราต้องแก้ปัญหานี้ในเวลาเชิงเส้น

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[5, 10, 20, 10, 0] เอาต์พุตจะเป็น True เพราะทุกรายการย่อยใน nums มีองค์ประกอบอย่างน้อยหนึ่งรายการซึ่งเกิดขึ้นเพียงครั้งเดียว [[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10, 20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0] ] ทั้งหมดมีองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบที่มีความถี่เท่ากับ 1

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

• กำหนดฟังก์ชัน has_unique() นี่จะเป็นทางซ้าย ขวา
• ถ้าซ้าย>=ขวา แล้ว
  • คืนค่า True
• นับ :=พจนานุกรมที่มีความถี่ของแต่ละองค์ประกอบที่แสดงเป็น nums[จากดัชนีซ้ายไปขวา]
• ถ้าความถี่ต่ำสุดจากการนับ> 1 แล้ว
  • คืนค่าเท็จ
• เริ่ม :=ซ้าย
• สำหรับดัชนีในช่วงจากซ้ายไปขวา ทำ
  • ถ้า counts[nums[index]] เท่ากับ 1 แล้ว
    • ถ้า has_unique(start, index - 1) เป็นเท็จ แล้ว
      • คืนค่าเท็จ
    • เริ่ม :=ดัชนี + 1
• ส่งคืน has_unique(เริ่ม, ขวา)
• จากวิธีหลัก ส่งคืน has_unique(0, size of nums - 1)

ตัวอย่าง

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

from collections import Counter
def solve(nums):
   def has_unique(left, right):
      if left >= right:
         return True

      counts = Counter(nums[left : right + 1])
      if min(counts.values()) > 1:
         return False

      start = left

      for index in range(left, right + 1):
         if counts[nums[index]] == 1:
            if not has_unique(start, index - 1):
               return False
            start = index + 1

      return has_unique(start, right)

   return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

อินพุต

[5, 10, 20, 10, 0]

ผลลัพธ์

True