Cho hai mảng số, viết hàm intersection() tính giao, trả về mảng chứa phần tử giao theo thứ tự bất kỳ. Mỗi phần tử xuất hiện số lần = min(số lần trong arr1, số lần trong arr2).
Ví dụ: arr1=[1,2,3,1], arr2=[1,3,1] => [1,3,1].
Nếu mảng đã sort có thể dùng two-pointer O(m+n). Với mảng chưa sort, dùng O(n^2): kiểm tra từng phần tử mảng nhỏ trong mảng lớn, tìm thấy thì push kết quả và xóa khỏi mảng lớn (gán undefined).
Ví dụ
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));Kết quả
Đầu ra trong console sẽ là:
[1, 2, 5, 3, 7, 7, 2]