Giả sử chúng ta có hai danh sách số là nums1 và nums2. Có một số phần tử không nhất thiết duy nhất. Nhưng hai danh sách này thực tế đại diện cho các hoán vị khác nhau của cùng một tập hợp số. Tuy nhiên, một số bị thiếu. Chúng ta phải tìm các số bị thiếu của hai danh sách này và in ra tất cả.
Vì vậy, nếu đầu vào là nums1 = [4,5,8,8,6,9] nums2 = [3,4,4,8,8,8,6,9,5,8], thì đầu ra sẽ là [3,4,8,8] vì ta thấy 3 không có trong nums1 nhưng có trong nums2, nên nó thiếu. 4 có trong cả hai nhưng trong nums2 có hai 4 mà nums1 chỉ có một, nên thiếu một 4. Tương tự nums2 có bốn 8, nums1 chỉ có 2, nên thiếu hai 8.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
- c1 := Counter chứa tần suất các phần tử trong nums1
- c2 := Counter chứa tần suất các phần tử trong nums2
- all_nums := set chứa tất cả các số khác biệt từ nums1 và nums2
- res := danh sách mới
- với mỗi n trong all_nums, thực hiện
- nếu n không trong c1, thì thêm n, c2[n] lần vào res
- ngược lại nếu n không trong c2, thì thêm n, c1[n] lần vào res
- ngược lại, nếu c1[n] != c2[n], thì thêm n, |c1[n]-c2[n]| lần vào res
- trả về res
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơ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))
Đầu vào
[4,5,8,8,6,9], [3,4,4,8,8,8,6,9,5,8]
Đầu ra
[3, 4, 8, 8]