Phần tử lớn thứ k trong luồng javascript

Thiết kế một lớp để tìm phần tử lớn thứ K trong một dòng số một cách hiệu quả. Lớp học nên có hai điều sau đây. ​

Hàm tạo của lớp phải chấp nhận một mảng số nguyên chứa các số ban đầu từ luồng và một số nguyên 'K'

Lớp sẽ hiển thị một hàm add(int num) sẽ lưu số đã cho và trả về số lớn nhất thứ K

Những gì tôi đã thử

tôi không biết làm thế nào để giải quyết vấn đề này

---

Tạo một mảng gồm K phần tử, điền trước nó bằng số nhỏ nhất mà nó có thể chứa.
Khi bạn nhận được một giá trị, hãy xem giá trị đó đã có trong mảng chưa. Nếu vậy, bỏ qua nó.
Kiểm tra xem nó có thấp hơn phần tử thấp nhất trong mảng không. Nếu vậy, bỏ qua nó.
Nếu không, hãy chèn nó vào mảng theo thứ tự đã sắp xếp. giữa giá trị thấp hơn và giá trị cao hơn hoặc ở vị trí cao nhất nếu cần.
Ở cuối luồng, giá trị thấp nhất trong mảng là giá trị cao nhất thứ K.

Bạn cần hiểu rằng Bài tập về nhà được đưa ra là có lý do. Và lý do chính là để chuẩn bị cho bạn các nhiệm vụ công việc trong thế giới thực

Ngoài ra, bạn thậm chí không cần google câu hỏi, nếu không, bạn đã tìm ra giải pháp như bên dưới trong vòng chưa đầy một phút

Phần tử lớn thứ K trong luồng - GeekforGeek[^]

Bạn phải hiểu rằng không có con đường tắt của Thành công

Thêm giải pháp của bạn ở đây

 B   I   U   S  small BIG code var  <   >   &  link [^] encode untab case indent outdent

Xem trước 0

thành viên hiện có

hoặc tham gia với chúng tôi

Tải xuống, Bình chọn, Nhận xét, Xuất bản

Email của bạn

Email này đang được sử dụng. Bạn có cần mật khẩu của bạn?

Mật khẩu tùy chọn

Khi trả lời câu hỏi, vui lòng.

1. Đọc kỹ câu hỏi.
2. Hiểu rằng tiếng Anh không phải là ngôn ngữ đầu tiên của mọi người, vì vậy hãy khoan dung với lỗi chính tả và ngữ pháp
3. Nếu một câu hỏi được diễn đạt kém thì hãy yêu cầu làm rõ, bỏ qua nó hoặc chỉnh sửa câu hỏi và khắc phục sự cố. Xúc phạm không được chào đón
4. Đừng bảo ai đó đọc hướng dẫn. Rất có thể họ có và không nhận được. Đưa ra câu trả lời hoặc chuyển sang câu hỏi tiếp theo

Let's work to help developers, not make them feel stupid.

Nội dung này, cùng với bất kỳ tệp và mã nguồn liên quan nào, được cấp phép theo Giấy phép Mở Dự án Code (CPOL)

Đưa ra một luồng số nguyên vô hạn, trả về phần tử đại diện cho phần tử lớn nhất của k'th trong luồng

Trong bài viết trước, chúng ta đã thảo luận về một số phương pháp để tìm k'th phần tử lớn nhất trong một mảng. Trong bài đăng này, chúng tôi được cung cấp một luồng vô hạn thay vì một mảng có độ dài cố định

 
Ví dụ:

Đầu vào. Dòng số nguyên vô hạn
 
4
5
12
8
9
10
20
42
…
 
Output:
 
Phần tử lớn thứ k là NA.
Phần tử lớn thứ k là NA.
Phần tử lớn thứ k là 4
Phần tử lớn thứ k là 5
Phần tử lớn thứ k là
The k’th largest element is 9
The k’th largest element is 10
The k’th largest element is 12
…

Thực hành vấn đề này

1. Giải pháp Brute-Force

Một giải pháp đơn giản là duy trì một mảng có kích thước k để lưu trữ các phần tử lớn nhất k hàng đầu trong số tất cả các phần tử gặp phải cho đến nay trong luồng. Mảng nên được sắp xếp theo thứ tự tăng dần để tìm phần tử lớn nhất k'th trong thời gian không đổi. Bây giờ, phần tử đầu tiên trong mảng đã sắp xếp là phần tử lớn nhất k'th

Ý tưởng là so sánh từng phần tử đến n trong luồng với phần tử gốc của min-heap k2. Nếu n lớn hơn k2, hãy thay thế k2 bằng n và gọi thủ tục Heapify trên gốc của đống đã sửa đổi. Nếu n nhỏ hơn k2, bỏ qua nó

Độ phức tạp về thời gian của heapify() là O(N), heappush() và heappop() đều là O(log N). Thao tác bật lên là O(log N) vì bạn cần sửa đổi vị trí của phần tử khác để duy trì đống

Phần tử lớn thứ K trong một luồng - LeetCode

Nâng cao kỹ năng mã hóa của bạn và nhanh chóng tìm được việc làm. Đây là nơi tốt nhất để mở rộng kiến ​​thức của bạn và chuẩn bị…

mật mã. com

Ghi chú. Khi câu hỏi yêu cầu giá trị thứ k, hãy nghĩ đến việc sử dụng Heap

Lấy ví dụ 1 làm ví dụ

Để có được mục lớn thứ 3 trong danh sách đã cho [4,5,8,2], chúng tôi lấy mục từ mục lớn nhất đến mục thứ 3 8 -> 5 -> 4, biến chúng thành một danh sách được xem xét. Và 2 sẽ không bao giờ được xem xét cho dù mục tiếp theo được thêm vào

Khi một mục được thêm vào, xác định xem nó có lớn hơn số nhỏ nhất trong danh sách được xem xét hay không, nếu có, hãy lấy ra mục nhỏ nhất trong danh sách được xem xét và đẩy mục đó vào danh sách