Cách tối ưu để tính số nguyên nào trong danh sách bị thiếu?

Question

Gần đây tôi đã tham gia một cuộc phỏng vấn nơi họ hỏi tôi những câu hỏi kỹ thuật. Một là cách bạn sẽ tính số nào trong danh sách độ dài n-1 bị thiếu. Danh sách chứa tất cả các số từ 1 đến n, ngoại trừ i trong đó 1 < = i < = n. Các con số không theo thứ tự. Giải pháp của tôi là cộng tất cả chúng lên, sau đó trừ đi từ việc tính toán các số từ 1 đến n, bằng cách thêm 1 đến n và nhân với n/2 hoặc (n-1)/2 khi thích hợp. Nhưng tôi có cảm giác rằng có một cách tốt hơn để làm điều đó. Giải pháp tối ưu là gì?

Answer 1

Câu trả lời của bạn là đủ tốt, theo ý kiến ​​của tôi.

Nhưng một số người - có lẽ người phỏng vấn của bạn là một trong số họ - đang lo lắng về tình trạng tràn và như vậy. Trong trường hợp đó, hãy sử dụng XOR thay vì bổ sung.

Để lấy XOR của các số nguyên từ 0 đến n, chỉ cần XOR cùng với các chỉ mục mảng khi bạn lặp lại. Với XOR của các số nguyên từ 0 đến n và XOR của các phần tử mảng, bạn chỉ XOR hai số nguyên tố đó lại với nhau để lấy phần tử còn thiếu.

P.S. Tổng các số nguyên từ 1 đến n luôn là (n + 1) * n/2

Answer 2

trong khi lặp qua mảng để tính tổng, bạn có thể kiểm tra xem liệu một số có lặp lại hay không.

Answer 3

Phương pháp của bạn hoàn toàn ổn. Nó là tối ưu cả về không gian và thời gian. Tràn có thể là vấn đề duy nhất với nó.

Một phương pháp khác có thể là sử dụng hàm băm. Tạo một hashSet ban đầu có các giá trị 1-> N. Bây giờ cho mỗi số bạn gặp phải trong danh sách - xóa giá trị đó khỏi hashSet. Cuối cùng, giá trị còn lại trong hashSet là giá trị bị thiếu.

Phương pháp này là O (N) về thời gian và không gian phức tạp. Phương pháp của bạn (chặn tràn) là O (N) trong thời gian và O (1) phức tạp. Yếu tố 'n' được thêm vào cho không gian là chi phí để loại bỏ tràn.

Answer 4

giải pháp của bạn là khá nhiều tối ưu với một thay đổi, như @Nemo chỉ ra tổng của các số nguyên từ 1 đến n luôn là (n+1) * n/2

Nó cũng có giá trị chỉ ra rằng cách tiếp cận của bạn là multi-thread có khả năng (và might phù hợp với các giá trị rất lớn của N), chia mảng thành từng phần, sau đó lấy tổng của mỗi phần mảng trong một chuỗi, sau đó thêm các phần tiền đó. Nó phụ thuộc vào chi phí của luồng được so sánh với việc thêm số vào một mảng.

Nếu bạn lo lắng về việc tràn và giá trị luôn luôn là int32 (như hầu hết các giá trị .Length bao gồm mảng) thì chỉ lưu trữ tổng dưới dạng int64, tổng của tất cả các giá trị nguyên dương (((long)int.MaxValue) +1L) * (int.MaxValue/2) = 2305843007066210304. trong một int64 với .MaxValue = 9223372036854775807.

Câu trả lời khác như được đề cập bởi những người khác là XOR từng mục và giữ một XOR đang chạy, nhưng sau đó bạn cần phải tính toán công thức để đạt được tổng XOR dự kiến ​​trong thời gian O(1).

Rất có thể người phỏng vấn đang tìm cách xem bạn có nhận được giải pháp O(N) với bộ nhớ O(1) (câu trả lời của bạn) thay vì sắp xếp mảng và chậm hơn nhiều cho các giá trị rất lớn là N.

Để cải thiện hơn nữa giải pháp của bạn trong mã, sẽ sử dụng con trỏ để truy cập mảng thay vì giá trị chỉ mục (nếu mã của bạn là C# sẽ là một cải tiến hợp lý).