เรามีสองอาร์เรย์ของตัวเลข และต้องเขียนฟังก์ชัน เช่น intersection() ที่คำนวณ intersection ของพวกเขาและคืนค่าอาร์เรย์ที่มีองค์ประกอบที่ intersect ในลำดับไหนก็ได้ แต่ละองค์ประกอบในผลลัพธ์ควรปรากฏหลายครั้งเท่ากับที่มันแสดงในทั้งสองอาร์เรย์
ตัวอย่าง − ถ้า
Input: arr1 = [1,2,3,1], arr2 = [1,3,1] Output: [1,3,1]
วิธีการ
ถ้าอาร์เรย์ถูกจัดเรียงแล้ว เราอาจใช้ two pointer approach ที่ชี้ที่ 0 เริ่มต้นของอาร์เรย์แต่ละอันและดำเนินต่อด้วยการเพิ่ม pointer ที่สอดคล้องและนั่นจะเป็น O(m+n) complex ว่าด้วยเวลา โดย m และ n คือขนาดอาร์เรย์
แต่เพราะเรามีอาร์เรย์ที่ไม่ได้จัดเรียง ไม่มีเหตุผลที่จะจัดเรียงอาร์เรย์แล้วใช้วิธีนี้ เราจะตรวจสอบทุกค่าของอันแรกกับอันที่สองและสร้าง intersection array นี้จะใช้เวลา O(n^2)
และโค้ดสำหรับทำนี้จะเป็น −
ตัวอย่าง
const arr1 = [1, 2, 43, 5, 3, 7, 7,8, 4, 2]; const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3]; const intersection = (arr1, arr2) => { const res = []; const { length: len1 } = arr1; const { length: len2 } = arr2; const smaller = (len1 < len2 ? arr1 : arr2).slice(); const bigger = (len1 >= len2 ? arr1 : arr2).slice(); for(let i = 0; i < smaller.length; i++){ if(bigger.indexOf(smaller[i]) !== -1){ res.push(smaller[i]); bigger.splice(bigger.indexOf(smaller[i]), 1, undefined); } }; return res; }; console.log(intersection(arr1 ,arr2));ผลลัพธ์
ผลลัพธ์ในคอนโซลจะเป็นดังนี้
[1, 2, 5, 3, 7, 7, 2]
