เรามี Numbers สองอาร์เรย์ และเราจำเป็นต้องเขียนฟังก์ชัน โดยพูดว่า intersection() ที่คำนวณจุดตัดของพวกมัน และส่งคืนอาร์เรย์ที่มีองค์ประกอบที่ตัดกันในลำดับใดก็ได้ แต่ละองค์ประกอบในผลลัพธ์ควรปรากฏหลายครั้งตามที่แสดงในอาร์เรย์ทั้งสอง
ตัวอย่างเช่น − ถ้า
Input: arr1 = [1,2,3,1], arr2 = [1,3,1] Output: [1,3,1]
แนวทาง
หากจัดเรียงอาร์เรย์แล้ว เราอาจใช้วิธีตัวชี้สองตัวโดยเริ่มแรกทั้งคู่ชี้ไปที่ 0 ที่จุดเริ่มต้นของอาร์เรย์ที่เกี่ยวข้อง และเราอาจดำเนินการเพิ่มตัวชี้ที่สอดคล้องกัน และนั่นจะเป็น O(m+n) ที่ซับซ้อน wrt เวลาที่ m และ n คือขนาดของอาร์เรย์
แต่เนื่องจากเรามีอาร์เรย์ที่ไม่เรียงลำดับ จึงไม่มีเหตุผลในการจัดเรียงอาร์เรย์ จากนั้นจึงใช้วิธีนี้ เราจะตรวจสอบทุกค่าของค่าแรกเทียบกับค่าที่สอง และสร้างชุดข้อมูลแยก สิ่งนี้จะทำให้เราเสียเวลา 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]
