การหาจุดตัดของอาร์เรย์ของสตริง - JavaScript

เรามี Numbers สองอาร์เรย์ และเราจำเป็นต้องเขียนฟังก์ชัน สมมติว่า intersection() ที่คำนวณจุดตัดของพวกมันและส่งคืนอาร์เรย์ที่มีองค์ประกอบที่ตัดกันในลำดับใดก็ได้ แต่ละองค์ประกอบในผลลัพธ์ควรปรากฏหลายครั้งตามที่แสดงในอาร์เรย์ทั้งสอง

ตัวอย่างเช่น −

หากอินพุตเป็น −

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];

จากนั้นผลลัพธ์ควรเป็น −

Output: ['world', 'you'];

แนวทาง

หากจัดเรียงอาร์เรย์แล้ว เราอาจใช้วิธีตัวชี้สองตัวโดยเริ่มแรกทั้งคู่ชี้ไปที่ 0 ที่จุดเริ่มต้นของอาร์เรย์ที่เกี่ยวข้อง และเราอาจดำเนินการเพิ่มตัวชี้ที่เกี่ยวข้องต่อไปได้ และนั่นจะเป็น O(m+n) ที่ซับซ้อน wrt เวลาที่ m และ n คือขนาดของอาร์เรย์

แต่เนื่องจากเรามีอาร์เรย์ที่ไม่เรียงลำดับ จึงไม่มีเหตุผลในการจัดเรียงอาร์เรย์และจากนั้นใช้วิธีนี้ เราจะตรวจสอบทุกค่าของค่าแรกเทียบกับค่าที่สอง และสร้างอาร์เรย์ทางแยก สิ่งนี้จะทำให้เราเสียเวลา O(n^2)

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];
const intersectElements = (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(intersectElements(arr1, arr2));

ผลลัพธ์

สิ่งนี้จะสร้างผลลัพธ์ต่อไปนี้ในคอนโซล -

[ 'world', 'you' ]