Đề bài
Danh sách chứa n số nguyên khác nhau được chọn từ 0, 1, …, n, nên chính xác có một số trong khoảng đó bị thiếu. Hãy tìm số đó. (Gợi ý: so sánh tổng kỳ vọng với tổng thực tế.)
Cài đặt hàm missing_number(numbers).
Đầu vào
numbers: n số nguyên khác nhau từ 0 đến n.
Đầu ra
Trả về số bị thiếu.
Ràng buộc
0 ≤ n ≤ 100.000
Ví dụ
Ví dụ 1
Đầu vào:
numbers = [3, 0, 1]
Kết quả mong đợi:
expected = 2Đầu vào:
std::vector<long long> numbers = {3, 0, 1};
Kết quả mong đợi:
long long expected = 2;Đầu vào:
long[] numbers = new long[] {3, 0, 1};
Kết quả mong đợi:
long expected = 2;Giải thích
n = 3, nên dãy là 0–3; số 2 bị thiếu.
Ví dụ 2
Đầu vào:
numbers = [0]
Kết quả mong đợi:
expected = 1Đầu vào:
std::vector<long long> numbers = {0};
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long[] numbers = new long[] {0};
Kết quả mong đợi:
long expected = 1;Giải thích
n = 1 và dãy là 0–1; số 1 bị thiếu.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Các số phải khớp với toàn bộ dải từ 0 đến n, trừ một giá trị bị thiếu.
Gợi ý 2
So sánh tổng của dải đầy đủ với tổng thực tế của mảng.
Gợi ý 3
Lưu ý trường hợp giá trị bị thiếu là 0 hoặc n.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.