Đề bài
The list holds n distinct numbers taken from 0, 1, …, n, so exactly one number in that range is missing. Find it. (Hint: compare the expected total with the actual total.)
Implement missing_number(numbers).
Input
numbers: n distinct numbers from 0 to n.
Output
Return the missing number.
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, so the range is 0–3; 2 is missing.
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 and the range is 0–1; 1 is missing.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
The numbers should match the full range from 0 through n except for one hole.
Gợi ý 2
Compare what the complete range would total against what the list actually totals.
Gợi ý 3
Watch for the case where the missing value is 0 or n.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
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.