Chúng tôi được yêu cầu viết một hàm JavaScript nhận vào một mảng các số có độ dài, chẳng hạn như n. Mảng chứa tất cả các số nguyên từ 0 đến n (bao gồm cả 0 và n), nhưng chỉ cần thiếu một số nguyên, nó có thể là bất kỳ số nào và mảng không được sắp xếp. Nhiệm vụ của hàm của chúng ta là tìm số còn thiếu và trả về trong thời gian tuyến tính và không gian không đổi.
Vì mảng chứa tất cả các số từ 0 đến n trừ một số nên chúng ta có thể chỉ cần tính tổng tất cả các phần tử của mảng theo thời gian tuyến tính.
Và sau đó chúng ta có thể trừ nó khỏi tổng của n số tự nhiên đầu tiên có thể được tính theo thời gian và không gian không đổi. Sự khác biệt giữa cả hai sẽ là số còn thiếu của chúng tôi.
Ví dụ
Sau đây là mã -
const arr = [3, 7, 8, 10, 11, 0, 2, 6, 1, 4, 5];
const findMissing = (arr = []) => {
const sum = arr.reduce((acc, val) => acc + val);
const { length: num } = arr;
const correctSum = (num * (num + 1)) / 2;
return diff = correctSum - sum;
return diff;
};
console.log(findMissing(arr)); Đầu ra
Sau đây là đầu ra của bảng điều khiển -
9