Các thuật toán tìm ra 2 số trùng nhau trong một mảng cho sẵn
Đề bài Cho 1 mảng với N + 1 số từ 1 đến N hãy tìm ra 2 số trùng nhau với điều kiện: Độ phức tạp nhỏ hơn O(N^2). Không làm thay đổi thứ tự các số trong mảng. Tiết kiệm bộ nhớ, tốt nhất là không sinh ra mảng mới. Lời giải Cách 1: Sử dụng Map Như chúng ta đã biết , vì map đảm bảo tính duy nhất cho một key, nên chúng ta có thể coi mỗi số là một key, chúng ta sẽ ánh xạ với số lần số đó xuất hiện trong mảng, nếu số nào có số lần xuất hiện lớn hơn 1 nghĩa là số đó bị trùng: function findAllDuplicates(arr) { const freq = new Map(); for (const v of arr) { freq.set(v, (freq.get(v) || 0) + 1); } const duplicates = []; for (const [value, count] of freq.entries()) { if (coun
Category:
Thuật toán
Post by:
Young Monkeys - Founder
Young Monkeys - Founder
Posted date:
1764682406000