การหาตัวเลขที่หายไปจากสองรายการ (Permutation with Missing)
nums1 และ nums2 เป็น permutation ของชุดตัวเลขเดียวกันแต่ขาดบางตัว หาตัวเลขที่หาย (รวมความถี่)
อัลกอริทึม
- นับความถี่ c1 ของ nums1, c2 ของ nums2
- รวมตัวเลขทั้งหมดใน all_nums
- สำหรับแต่ละ n ใน all_nums:
- ถ้า n ไม่อยู่ใน c1 → เพิ่ม n จำนวน c2[n] ครั้ง
- ถ้า n ไม่อยู่ใน c2 → เพิ่ม n จำนวน c1[n] ครั้ง
- ถ้าอยู่ทั้งคู่แตกต่างความถี่ → เพิ่ม n จำนวน |c1[n]-c2[n]| ครั้ง
ตัวอย่างโค้ด
from collections import Counter
def solve(nums1, nums2):
c1 = Counter(nums1)
c2 = Counter(nums2)
all_nums = set(nums1) | set(nums2)
res = []
for n in all_nums:
if n not in c1:
res = res + [n] * c2[n]
elif n not in c2:
res = res + [n] * c1[n]
else:
if c1[n] != c2[n]:
res = res + [n] * abs(c1[n] - c2[n])
return res
nums1 = [4,5,8,8,6,9]
nums2 = [3,4,4,8,8,8,6,9,5,8]
print(solve(nums1, nums2))
ผลลัพธ์
[3, 4, 8, 8]
คำอธิบาย
- 3: อยู่ใน nums2 4 ครั้ง, nums1 0 ครั้ง → เพิ่ม 3, 4 ครั้ง (แต่โค้ดเพิ่ม c2[3]=1 ครั้ง? ตรวจสอบ: nums2 มี 3 อยู่ 1 ตัว → เพิ่ม 1 ตัว)
- 4: nums1=1, nums2=2 → เพิ่ม 1 ตัว
- 8: nums1=2, nums2=4 → เพิ่ม 2 ตัว
- ผลลัพธ์: [3, 4, 8, 8]
