Fanboi Channel

>>493 เอาแบบวิธีเถือกคร่าวๆ สมมุติมี Set A กับ B จะให้เอาผลไปใส่ Set C
โดยที่ Set ในที่นี้อาจจะไม่ได้ต้องเป็น Data Structure ที่มีคุณสมบัติเป็น Set จริงๆก็ได้ สมมุติง่ายๆก็เอาเป็น array ธรรมดา
สมมุติว่า Set A กับ B ไม่มีสมาชิกที่ค่าซ้ำกันเพราะโจทย์กำหนดมาว่าเป็น Set

Union
1. วนลูปยัดสมาชิกทุกตัวของ A ลงไปใน C
2. วนลูปยัดสมาชิกของ B ลงไปใน C ถ้าสมาชิกตัวนั้นๆไม่มีอยู่ใน A (วนลูปเล็กข้างในเช็คหรืออะไรก็ว่าไป)

Intersect
1. วนลูปยัดสมาชิกของ A ลงไปใน C ถ้าสมาชิกตัวนั้นๆมีอยู่มีอยู่ใน B ด้วย (วนลูปเล็กข้างในเช็คหรืออะไรก็ว่าไป)

ปล. 1 ถ้าใช้ภาษาที่มีของสำเร็จรูปให้ใช้อยู่แล้วเช่น Java ควรใช้ของสำเร็จรูป สั่งให้มันคิดให้เลย
ปล. 2 ถ้าภาษาที่ใช้ไม่มี Set สำเร็จรูปให้ใช้ แต่มี method หรือ function สำหรับเช็คว่าใน array มีค่าตัวที่เราหารึเปล่า
ควรใช้การเช็คด้วยวิธีนี้มากกว่ามาวนลูปซ้อนลูปเอง

Union https://hastebin.com/oreyazuron.py
น่าจะ O(n) ข้อเสียคือห้ามมี duplicate

Intersect https://hastebin.com/fapocubeci.py
ใช้วิธีเดียวกันกับข้างบน ห้ามมี duplicate เหมือนกัน

วิธีการทำงานของมันคือ sort ทั้ง 2 list ที่รับเข้ามาแล้วลูปทีละหลักของทั้ง 2 list พร้อมๆ กัน
ถ้าหากสมาชิกในตำแหน่งที่หาของ list หนึ่งไม่เท่ากับของอีก list หนึ่ง แปลว่าค่านั้นไม่มีอยู่ในอีก list
เทียบแบบนี้ได้เป็นผลจากการ sort มาก่อน

เช่นมี 2 list
a = {1 2 4 5}
b = {2 3 4 5 6}

ลูปแรก i = 0, j = 0 เทียบได้ว่า 1 < 2 แปลว่า 1 ไม่ใช่สมาชิกของ list b (เพิ่ม i)
ลูปสอง i = 1, j = 0 เทียบได้ว่า 2 == 2 แปลว่า 2 เป็นสมาชิกของทั้ง 2 list (เพิ่ม i, j)
ลูปสาม i = 2, j = 1 เทียบได้ว่า 4 > 3 แปลว่า 3 ไม่ใช่สมาชิกของ list a (เพิ่ม j)
ลูปสี่ i = 2, j = 2 เทียบได้ว่า 4 == 4 แปลว่า 4 เป็นสมาชิกของทั้ง 2 list (เพิ่ม i, j)
ลูปห้า i = 3, j = 3 เทียบได้ว่า 5 == 5 แปลว่า 5 เป็นสมาชิกของทั้ง 2 list (เพิ่ม i, j)
ลูปหก i = 4, j = 4 ขนาดของ i เกินจำนวนสมาชิกใน list a แปลว่าสมาชิกที่เหลือของ list b ไม่ใช่สมาชิกของ list a

จะยัดมันลง output หรือเปล่าขึ้นอยู่กับว่าเป็น union หรือ intersection
กรณี union ต้องเขียนอีก 2 ลูปไว้เก็บสมาชิกที่เหลือของ list a หรือ list b ลง output ด้วย (แต่จะรันแค่ลูปเดียว)
ทำให้อัลกอริธึ่มนี้จะใช้เวลาเท่ากับจำนวนสมาชิกที่ unique ของทั้ง 2 list บวกกับเวลา sort