Tìm giao nhau của các chuỗi khác nhau trong JavaScript

Tìm giao nhau của các chuỗi khác nhau trong JavaScript

Chúng ta có hai mảng số, và chúng ta cần viết một hàm intersection() tính giao của chúng và trả về một mảng chứa các phần tử giao nhau theo bất kỳ thứ tự nào. Mỗi phần tử trong kết quả nên xuất hiện bao nhiêu lần nó xuất hiện trong cả hai mảng.

Ví dụ:

Nếu đầu vào là:

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

Thì kết quả đầu ra nên là:

['world', 'you'];

Phương pháp:

Nếu các mảng đã được sắp xếp, chúng ta có thể dùng cách hai con trỏ (two-pointer) với cả hai ban đầu trỏ đến 0 đầu của mảng tương ứng và chúng ta có thể tiến hành tăng con trỏ tương ứng và đó sẽ phức tạp O(m+n) về thời gian với m và n là kích thước mảng.

Nhưng vì chúng ta có mảng không sắp xếp, không có logic nào trong việc sắp xếp mảng rồi dùng cách đó, chúng ta sẽ kiểm tra mọi giá trị của mảng đầu tiên đối với mảng thứ hai và xây dựng mảng giao nhau.

Điều này sẽ tốn O(n^2) thời gian.

Do đó, hãy viết mã cho hàm này:

Ví dụ

Mã thực hiện như sau:

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));

Đầu ra

Kết quả trong console sẽ là:

[ 'world', 'you' ]