Thuật toán tìm số thứ tự của các khoảng trống dài nhất trong một chuỗi đã cho

Question

Tìm kiếm một thuật toán để tìm độ dài của khoảng trống dài nhất trong một chuỗi đã cho xem xét ít ký tự nhất có thể?

Gợi ý: Chương trình của bạn sẽ trở nên nhanh hơn khi độ dài của chuỗi khoảng trống tăng lên.

Tôi biết các giải pháp mà là O (n) .. Nhưng tìm kiếm thêm giải pháp tối ưu

Answer 1

Nhưng trong trường hợp xấu nhất (khi tất cả các nhân vật đều trống), bạn phải kiểm tra tất cả các nhân vật. Vì vậy, nó không thể tốt hơn O (n) trong phức tạp.

Lý do: giả sử toàn bộ chuỗi trống, bạn chưa kiểm tra N ký tự và thuật toán của bạn xuất ra n. Sau đó, nếu bất kỳ ký tự không được kiểm tra nào không được để trống, câu trả lời của bạn sẽ sai. Vì vậy, đối với đầu vào cụ thể này, bạn phải kiểm tra toàn bộ chuỗi.

Answer 2

Bạn sẽ không thể tìm thấy giải pháp phức tạp hơn O (n) vì bạn cần phải vượt qua mọi ký tự trong trường hợp xấu nhất với chuỗi đầu vào có tối đa 0 hoặc 1 khoảng trống liên tiếp, hoặc là khoảng trắng hoàn toàn.

Tuy nhiên, bạn có thể thực hiện một số tối ưu hóa nhưng vẫn được coi là O (n).

Ví dụ:

Cho M là kết quả dài nhất hiện tại cho đến khi bạn đi qua danh sách của mình. Cũng giả sử bạn có thể truy cập các phần tử đầu vào trong O (1), ví dụ bạn có một mảng làm đầu vào.

Khi bạn nhìn thấy khoảng trắng, bạn có thể bỏ qua phần tử M nếu current + M là khoảng trắng. Chắc chắn không có khoảng trắng dài hơn M có thể chứa bên trong.

Và khi bạn nhìn thấy một ký tự trắng, nếu current + M-1 không phải là khoảng trắng bạn biết bạn không có chạy dài nhất o bạn cũng có thể bỏ qua trong trường hợp đó.

Answer 3

Bạn đã bao giờ làm gì, trường hợp xấu nhất sẽ luôn là o (n) - nếu những khoảng trống đó nằm ở phần cuối cùng của chuỗi ... (hoặc phần "đã kiểm tra" cuối cùng của chuỗi).

Answer 4

Ý tưởng rõ ràng: bạn có thể nhảy qua vị trí K + 1 (trong đó K là chuỗi không gian dài nhất hiện tại) và quét lại nếu bạn tìm thấy một không gian.

Bằng cách này, bạn có điều gì đó về (n + n/M)/2 = n (M + 1)/2M vị trí được chọn.

Chỉnh sửa:
Một ý tưởng khác là áp dụng một loại tìm kiếm nhị phân. Điều này giống như sau: đối với một số k nhất định, bạn thực hiện quy trình kiểm tra xem có chuỗi không gian có độ dài > = k hay không. Điều này có thể đạt được trong các bước O (n/k). Sau đó, bạn cố gắng tìm số tối đa k với tìm kiếm nhị phân.

Edit:
Trong tìm kiếm hậu quả, bạn có thể sử dụng sự hiểu biết rằng trình tự của một số chiều dài k đã tồn tại, và bắt đầu bỏ qua tại k ngay từ đầu.

Answer 5

Không có cách nào để làm cho nó nhanh hơn O(N) trong trường hợp xấu nhất. Tuy nhiên, đây là một vài tối ưu hóa, giả sử chỉ mục dựa trên 0.

1. Nếu bạn đã có một chuỗi hoàn chỉnh các L khoảng trống (bằng cách hoàn tất Ý tôi là một chuỗi đó không phải là một dãy con của một chuỗi lớn hơn), và L ít nhất là lớn như một nửa kích thước của chuỗi, bạn có thể dừng.
2. Nếu bạn có một chuỗi hoàn chỉnh các L khoảng trống, một khi bạn nhấn một không gian tại vị trí i kiểm tra nếu các nhân vật ở vị trí i + L cũng là một không gian. Nếu có, tiếp tục quét từ vị trí i chuyển tiếp vì bạn có thể tìm thấy chuỗi lớn hơn - tuy nhiên, nếu bạn gặp phải không gian cho đến vị trí i + L, thì bạn có thể chuyển trực tiếp đến i + L + 1. Nếu nó không phải là một không gian, không có cách nào bạn có thể xây dựng một chuỗi lớn hơn bắt đầu từ i, do đó quét chuyển tiếp bắt đầu từ i + L + 1.
3. Nếu bạn có một chuỗi các khoảng trống đầy đủ L và bạn đang ở vị trí i và bạn có k vị trí cần kiểm tra và k <= L, bạn có thể ngừng tìm kiếm của mình, vì rõ ràng không có cách nào bạn có thể tìm thấy bất cứ điều gì tốt hơn nữa.

Để chứng minh rằng bạn không thể làm cho nó nhanh hơn O(N), hãy xem xét một chuỗi không chứa dấu cách. Bạn sẽ phải truy cập từng nhân vật một lần, vì vậy nó là O(N). Tương tự với chuỗi không chứa gì ngoài dấu cách.