Làm thế nào để tìm kiếm một mảng lớn cho một đối tượng?

Question

Tôi đã có một cuộc phỏng vấn hôm nay, tôi được hỏi tìm kiếm một số bên trong một mảng như thế nào, tôi đã hỏi binarysearch, anh ấy hỏi tôi về một mảng lớn có hàng nghìn bịch (ví dụ như Stocks) tìm kiếm ví dụ theo giá cổ phiếu , Tôi nói binarysearch một lần nữa, ông nói phân loại một mảng của hàng ngàn sẽ mất rất nhiều thời gian trước khi áp dụng binarysearch.

Bạn có thể vui lòng chịu đựng và dạy tôi cách tiếp cận vấn đề này không? cảm ơn trợ giúp của bạn được đánh giá cao.

Answer 1

Còn có các thuật toán sắp xếp nhanh khác. Shell ngắn xuất hiện trong đầu bạn.

http://en.wikipedia.org/wiki/Shellsort

Answer 2

Tôi không chắc chắn những gì ông có trong tâm trí.

Nếu bạn chỉ muốn tìm số một lần và bạn không có đảm bảo về việc liệu mảng có được sắp xếp hay không, thì tôi không nghĩ bạn có thể đánh bại tìm kiếm tuyến tính. Trung bình bạn sẽ cần phải tìm kiếm nửa chừng trước khi bạn tìm thấy giá trị, nghĩa là thời gian chạy dự kiến ​​O (N); khi sắp xếp, bạn phải chạm vào từng giá trị đơn lẻ ít nhất một lần và có thể nhiều hơn thế, nghĩa là thời gian chạy dự kiến ​​O (N log N).

Nhưng nếu bạn cần phải tìm nhiều giá trị thì thời gian đã phân loại sẽ trả nhanh chóng. Với một mảng được sắp xếp, bạn có thể tìm kiếm nhị phân trong thời gian O (log N), vì vậy chắc chắn bằng tìm kiếm thứ ba bạn đang đi trước nếu bạn đã đầu tư thời gian để sắp xếp.

Bạn có thể làm tốt hơn nữa nếu bạn được phép xây dựng các cấu trúc dữ liệu khác nhau để giúp giải quyết vấn đề. Bạn có thể xây dựng một số loại chỉ mục, chẳng hạn như bảng băm; nhưng cấu trúc dữ liệu vô địch cho loại vấn đề này có lẽ sẽ là một số loại cấu trúc cây. Sau đó, bạn có thể chèn các giá trị mới vào cây nhanh hơn bạn có thể chắp thêm các giá trị mới và sắp xếp lại mảng, và tra cứu vẫn sẽ là O (log N) để tìm bất kỳ giá trị nào. Có nhiều loại cây khác nhau: cây nhị phân, cây B, trie, v.v.

Nhưng như @Hot Licks cho biết, bảng băm thường được sử dụng cho loại điều này và nó khá rẻ để cập nhật: bạn chỉ cần thêm một giá trị vào mảng chính và cập nhật bảng băm để trỏ đến giá trị mới. Và một bảng băm là rất gần với O (1) thời gian, mà bạn không thể đánh bại. (Bảng băm là O (1) nếu không có xung đột băm, giả sử một thuật toán băm tốt và bảng băm đủ lớn sẽ hầu như không có xung đột. Tôi nghĩ bạn có thể nói rằng bảng băm là O (N) trong đó N là số lần va chạm băm trung bình trên mỗi "thùng". Nếu tôi sai về điều đó tôi mong đợi được sửa chữa rất nhanh; đây là StackOverflow!)

Answer 3

Quicksort cũng khá tốt.

http://en.wikipedia.org/wiki/Quicksort

Answer 4

Tôi nghĩ rằng người phỏng vấn muốn bạn để phân tích dưới trường hợp khác nhau về tình trạng ban đầu mảng, những thuật toán, bạn sẽ sử dụng. Nguyên nhân, bạn phải biết bạn có thể xây dựng một bảng băm và sau đó O (1) có thể tìm số, hoặc khi mảng được sắp xếp (thời gian sắp xếp có thể có liên quan), bạn có thể sử dụng binarysearch hoặc sử dụng một số cấu trúc dữ liệu khác hoàn thành công việc.

Answer 5

Tôi đã hỏi một twist question.The tương tự là để tìm kiếm trong sắp xếp và sau đó một mảng không được phân loại là .These câu trả lời của tôi không được chấp nhận tất cả

1. Đối với sắp xếp tôi đề nghị chúng ta có thể tìm thấy trung tâm và thực hiện tìm kiếm tuyến tính .Tìm kiếm nhị phân cũng sẽ hoạt động tại đây
2. Đối với các tuyến tính được đề xuất chưa được phân loại lại.
3. Sau đó, tôi đề xuất Nhị phân là loại sai.
4. Đề xuất lưu trữ mảng trong một bộ băm và sử dụng băm. (Không được chấp nhận vì độ phức tạp không gian cao)
5. Tôi đã đề xuất Tree Set là một cây Đỏ đen khá tốt để tra cứu. (Không được chấp nhận vì độ phức tạp không gian cao)
6. Sao chép vào Arraylist etch cũng được coi là trên không.

Cuối cùng, tôi nhận được phản hồi tiêu cực. Mặc dù chúng ta có thể nghĩ rằng một trong các giải pháp trên là giải pháp nhưng chắc chắn có một cái gì đó đặc biệt trong tìm kiếm tuyến tính mà tôi đang thiếu.

Để lưu ý việc sắp xếp trước khi tìm kiếm cũng là một chi phí đặc biệt nếu bạn đang sử dụng bất kỳ cấu trúc dữ liệu bổ sung nào ở giữa.

Mọi nhận xét đều được hoan nghênh.