โปรแกรมหาจำนวนค่าที่ไม่ซ้ำกันน้อยที่สุดหลังลบ k อิลิเมนต์ด้วย Python

สมมติว่าเรามีอาร์เรย์ nums และตัวเลข k เราต้องหาจำนวนค่าที่ไม่ซ้ำกัน (unique) ที่น้อยที่สุดหลังจากลบอิลิเมนต์ออกไปก็พอดี k ตัว

เช่น nums = [5,4,2,2,4,4,3] k = 3 ผลลัพธ์คือ 2 เพราะลบ 5, 3 และหนึ่งใน 2 หรือ 4 จะเหลือแค่ 2 และ 4

ขั้นตอนการแก้ปัญหา

• นับความถี่ของแต่ละตัวเลขใน dictionary
• count = จำนวนค่าที่ไม่ซ้ำกัน (ขนาด dictionary)
• เรียงความถี่จากน้อยไปมาก
• วนลูปแต่ละ frequency:
  • k -= frequency
  • ถ้า k < 0: คืน count (ลบไม่หมดกลุ่มนี้)
  • มิฉะนั้น: count -= 1 (ลบกลุ่มนี้หมดได้)
• คืนค่า count

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

def solve(nums, k):
    dictionary = {}
    for num in nums:
        if num not in dictionary:
            dictionary[num] = 1
        else:
            dictionary[num] += 1
    count = len(dictionary)
    for frequency in sorted(dictionary.values()):
        k -= frequency
        if k < 0:
            return count
        else:
            count -= 1
    return count

nums = [5,4,2,2,4,4,3]
k = 3
print(solve(nums, k))

ข้อมูลเข้า

[5,4,2,2,4,4,3], 3

ข้อมูลออก

2