สมมติว่าเรามีอาร์เรย์สองอันคือ A และ B มีองค์ประกอบอยู่บ้าง เราต้องหาส่วนร่วมของพวกมัน เช่นถ้า A = [1, 4, 5, 3, 6] และ B = [2, 3, 5, 7, 9] ส่วนร่วมจะเป็น [3, 5]
วิธีการแก้ปัญหา
- รับอาร์เรย์สองอัน A และ B
- ถ้าความยาวของ A น้อยกว่าความยาวของ B ให้สลับกัน
- คำนวณความถี่ขององค์ประกอบในอาร์เรย์และเก็บไว้ใน m
- สำหรับแต่ละองค์ประกอบ e ใน B ถ้า e มีอยู่ใน m และความถี่ไม่เป็นศูนย์:
- ลดความถี่ m[e] ลง 1
- นำ e ไปใส่ในอาร์เรย์ผลลัพธ์
- คืนค่าอาร์เรย์ผลลัพธ์
ตัวอย่างโค้ด
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
m = {}
if len(nums1) < len(nums2):
nums1, nums2 = nums2, nums1
for i in nums1:
if i not in m:
m[i] = 1
else:
m[i] += 1
result = []
for i in nums2:
if i in m and m[i]:
m[i] -= 1
result.append(i)
return result
ob1 = Solution()
print(ob1.intersect([1,4,5,3,6], [2,3,5,7,9]))
อินพุต
[1,4,5,3,6] [2,3,5,7,9]
เอาต์พุต
[3,5]
