Thuật toán hiệu quả để tìm tên có sẵn đầu tiên

Question

Tôi có một mảng chứa tên các mục. Tôi muốn cung cấp cho người dùng tùy chọn tạo mục mà không chỉ định tên của họ, vì vậy chương trình của tôi sẽ phải cung cấp tên mặc định duy nhất, như "Mục 1".

Thách thức là tên phải là duy nhất vì vậy tôi phải kiểm tra tất cả các mảng cho tên mặc định đó, và nếu có một mục có cùng tên tôi phải đổi tên thành "Mục 2" và cho đến khi tôi tìm thấy một tên có sẵn.

Các giải pháp hiển nhiên sẽ là một cái gì đó như thế:

String name = "Item "; 
for (int i = 0; !isAvailable(name + i) ; i++); 

Vấn đề của tôi với thuật toán đó là nó chạy ở O (N^2).

Tôi tự hỏi nếu có một thuật toán được biết đến (hoặc mới) hiệu quả hơn để giải quyết trường hợp này.

Nói cách khác, câu hỏi của tôi là: Có bất kỳ thuật toán nào tìm thấy số lớn hơn 0 không có liều KHÔNG tồn tại trong một mảng nhất định và chạy ít hơn N^2 không?

Answer 1

Bạn chắc chắn có thể làm điều đó trong thời gian O (N) thời gian, N là số các mục trong mảng của bạn:

• Một trong những "khoản 1", "khoản 2", ... "Item N +1 "phải miễn phí, vì vậy hãy tạo một mảng cờ N + 1.
• Traverse các mục và cho mỗi tên nếu nó có dạng "Mục k" với 0 < k < = N + 1, đặt cờ đó.
• Quét mảng cờ cho cờ rõ ràng đầu tiên.

Yêu cầu bộ nhớ bổ sung là N + 1 bit, chắc chắn sẽ đánh bại bất kỳ cấu trúc dữ liệu nào thực sự lưu trữ tất cả các tên N.

Answer 2

Có, có.

Đầu tiên sắp xếp mảng. Sau đó chạy qua nó và trả về phần tử đầu tiên có giá trị không bằng với chỉ mục của nó (cộng 1). Sắp xếp là O (n log n), bước cuối cùng là O (n), do đó toàn bộ điều là O (n log n).

Nếu bạn đặt tất cả các mục vào bảng băm, bạn có thể làm điều đó bằng O (n) với chi phí của một số không gian và một bước O (1) bổ sung khi tạo mục mới. Vì mỗi phần tử cần được truy cập, O (n) rõ ràng là tối ưu.

Tôi muốn được xem liệu có cách O (n) để thực hiện việc này không, mà không cần bằng bất kỳ cấu trúc dữ liệu "liên tục" nào như bảng băm. (Và giả sử các số nguyên không bị chặn, nếu không, một loại nhóm có thể được sử dụng như một thuật toán phân loại O (n)).

Answer 3

Tại sao không chỉ theo dõi số lượng tối đa cho đến ngày và khi nào bạn cần số mới, hãy tăng số tiền đó?

Answer 4

Chèn tất cả các tên hiện có vào bảng băm. Lặp lại vòng lặp của bạn, nhưng thực hiện isAvailable kiểm tra bảng băm. Giả sử một hash khá, đó là O (nh) trong đó h là chi phí để đánh giá băm.

Answer 5

Bạn có thể thử làm như sau:

đầu tiên:

• vòng qua danh sách, và nhận được tất cả các mục được đánh số, đây là độ phức tạp N
• cho tất cả các mục được đánh số, đặt mục trong một cái cây (trong C++: std :: map), đây là nhật ký phức tạp (N)

Vì vậy, bây giờ bạn đã xây dựng một bản đồ với số đã sử dụng, với độ phức tạp "N x log (N)"

Tiếp theo, lặp lại cây và ngay sau khi bạn nhìn thấy 'lỗ', hãy sử dụng số. Trường hợp xấu nhất là phức tạp N.

Vì vậy, tổng thể, độ phức tạp là N log (N) + N hoặc đơn giản: N log (N).

Answer 6

Nếu chỉ có một người dùng truy cập vào mảng này, tại sao không sử dụng số nanoseconds? Điều này, tất nhiên, giả định rằng người sử dụng là nhiều hơn chậm hơn so với một máy tính, mà có vẻ là một giả định an toàn.

Bằng cách đó, bạn có chi phí O (1) để xác định tên duy nhất.

Answer 7

Một cách tiếp cận logarit thời gian, giả định rằng bạn không bao giờ rời khỏi "lỗ" bởi mục xóa:

// Inverse binary search for the last one. 
int upperBound = 1; 
while(isInUse(upperBound)) upperBound *= 2; 

// Standard binary search for the end once we have a ballpark. 
int lowerBound = upperBound/2; 
while(lowerBound < upperBound - 1) 
{ 
    int midpoint = (lowerBound + upperBound)/2; 
    if (isInUse(midpoint)) 
     lowerBound = midpoint; 
    else 
     upperBound = midpoint; 
} 
return upperBound; 

Nếu số mặt hàng có thể được giải phóng bằng cách xóa, không có gì ngắn của tìm kiếm tuyến tính sẽ làm việc trừ khi bạn cũng giữ một "danh sách miễn phí" và chọn từ đó.