Bài viết này sẽ dạy chúng ta tìm phần tử lớn thứ k trong một mảng chưa sắp xếp. Có nhiều cách khác nhau để tìm lời giải cho bài toán đã cho. Các thực hành tốt nhất có thể được thảo luận dưới đây
Bài toán - Xét một mảng chưa sắp xếp có N phần tử. Một số k nhỏ hơn kích thước của mảng được đưa ra;
Ví dụ
Cách tiếp cận 1. Phương pháp đơn giản nhất mà tôi nghĩ đến là sắp xếp mảng đã cho và trả về giá trị được yêu cầu. Chúng ta có thể tìm ra giải pháp trong thời gian O[N Log N] bằng cách sử dụng Sắp xếp đống hoặc Sắp xếp hợp nhất
Giả sử mảng không có phần tử giống nhau
Trong C++
Đầu ra mẫu
The 3th largest element = 15
trong C
Đầu ra mẫu
The 4th largest element = 12
Trong Python
Đầu ra mẫu
The 5th largest element = 8
mã C++
Đầu ra mẫu
My set = {2, 4, 5, 10, 12, 18, 22, 36, 54}
The 3th largest element = 22
Mã Python
đầu ra
My set = {8, 9, 10, 12, 15, 17, 22, 26, 27, 28, 29}
The 5th largest element = 22
Cách tiếp cận 3 - Sử dụng Max-Heap
Phần tử lớn thứ k có thể được tìm thấy với sự trợ giúp của heap. Ở đây, chúng tôi đã sử dụng heap tối đa; . Chúng tôi làm theo các bước tương tự k-1 lần. Sau đó, phần tử thứ k được tìm thấy tại gốc chỉ số = 0
Mã C++
đầu ra
The 2th largest element = 16
Mã C
đầu ra
The 3th largest element = 12
Cách tiếp cận 4 - Sử dụng Min Heap
Trong phương pháp này, chúng ta tạo một heap tối thiểu với k số phần tử và giá trị nhỏ nhất của nó [phần tử gốc] sẽ là giá trị lớn thứ k. Nếu mảng có nhiều hơn k phần tử thì ta kiểm tra từng phần tử xem có lớn hơn phần tử gốc của heap hay không, các phần tử còn lại ta làm theo các bước sau
- Nếu phần tử sẽ nhỏ hơn gốc nghĩa là giá trị lớn thứ k vẫn là phần tử gốc và ta kiểm tra điều kiện cho phần tử tiếp theo
- Nếu phần tử lớn hơn gốc có nghĩa là phần tử gốc không phải là giá trị lớn thứ k và chúng tôi thay thế gốc bằng phần tử và gọi min-heapify tại chỉ mục gốc
- Khi kết thúc thực thi, chúng tôi sẽ trả về phần tử gốc, đây sẽ là giá trị lớn thứ k
Độ phức tạp về thời gian của phương pháp này là T[n] = klogk + [n-k]logk
Và độ phức tạp không gian = O[k]
mã C++
đầu ra
My array = {12, 15, 17, 23, 9, 16, 7, 45, 6, 42, 33}
The 5th largest value = 17
mã C
đầu ra
________số 8
Cách tiếp cận 5 - Sắp xếp nhanh từng phần
Trong cách tiếp cận này, chúng tôi sử dụng ý tưởng sắp xếp nhanh để tìm phần tử lớn thứ k trong mảng. Như chúng ta đã biết, sắp xếp nhanh chọn một phần tử trục, đặt nó vào đúng chỉ mục của nó và lặp lại đệ quy quy trình tương tự cho đến khi mảng được sắp xếp. Tương tự, ta thực hiện các bước tương tự nhưng không thực hiện đầy đủ thao tác sắp xếp nhanh. Khi trục chính là giá trị lớn thứ k, chúng tôi sẽ dừng thực thi và in giá trị cần thiết. Độ phức tạp thời gian tồi tệ nhất của phương pháp này là O[n^2] và độ phức tạp thời gian trung bình là O[N logN]. Chúng tôi đạt được kết quả mong muốn trong thời gian ngắn hơn so với mức độ phức tạp trung bình của trường hợp
Cho một mảng số nguyên, A[] và một số nguyên K. Nhiệm vụ là trả về phần tử lớn thứ K trong một mảng
ví dụ
Đầu vào. A[] = {1, 2, 6, 4, 5}, K = 3
Đầu ra. 4
Giải thích. Được cung cấp trong hình trên
Bối rối về công việc tiếp theo của bạn?
Trong 3 bước đơn giản, bạn có thể tìm thấy lộ trình nghề nghiệp được cá nhân hóa của mình trong lĩnh vực Phát triển phần mềm MIỄN PHÍ
Mở rộng trong thẻ mới
Đầu vào. A[] = {3, 2, 1, 5, 6, 4}, K = 2
Đầu ra. 5
Cách tiếp cận 1. Loại
Cách đơn giản nhất để giải quyết vấn đề này là chỉ cần sắp xếp mảng đã cho theo thứ tự giảm dần và trả về phần tử thứ K từ đầu mảng
Mã C++
int kthLargest[vector < int > & arr, int size, int K] {
sort[arr.begin[], arr.end[], greater < int > []];
return arr[K - 1];
}Mã Java
The 4th largest element = 120
Mã Python
The 4th largest element = 121
Độ phức tạp về thời gian. O[NlogN], trong đó N là kích thước của mảng.
Độ phức tạp của không gian. O[1], vì không sử dụng thêm dung lượng.
Cách tiếp cận 2. đống
Phương pháp sắp xếp và tìm phần tử lớn thứ K trước đây rất tốn kém. Vì nhiệm vụ là trả về phần tử lớn thứ K, nên ý tưởng sẽ là duy trì cấu trúc dữ liệu giữ cho các phần tử của mảng theo thứ tự được sắp xếp, cùng với việc giảm độ phức tạp về thời gian
Ý tưởng là sử dụng max-heap. Vì max-heap giữ tất cả các phần tử theo thứ tự được sắp xếp, nên vấn đề chỉ cần chuyển đổi để in phần tử thứ K của max-heap
Hãy để chúng tôi cố gắng hiểu điều này với sự giúp đỡ của một ví dụ
thuật toán
- Khởi tạo một đống tối đa
- Chèn tất cả các phần tử của mảng đã cho vào heap tối đa
- Trích xuất các phần tử K – 1 đầu tiên từ heap
- In phần tử trên cùng của heap tối đa
Mã C++
The 4th largest element = 122
Mã Java
The 4th largest element = 123
Mã Python
The 4th largest element = 124
Độ phức tạp về thời gian. O[K + [N – K] * log[K] ], trong đó N là kích thước của mảng.
Độ phức tạp của không gian. O[K], vì đống được sử dụng.
Cách tiếp cận 3. Sử dụng Chọn nhanh
Cách tiếp cận là sử dụng cách tiếp cận chọn nhanh. Phương pháp này rất giống với phương pháp sắp xếp nhanh
Có thể thấy rõ ràng rằng phần tử lớn thứ K giống như phần tử nhỏ nhất thứ [N – K], trong đó N là kích thước của mảng đã cho. Do đó, ta có thể áp dụng cách tiếp cận nhỏ nhất thứ K cho bài toán này
Đầu tiên, phải chọn một phần tử trục, tương tự như những gì chúng ta làm trong quicksort. Nó có thể được thực hiện bằng thuật toán phân vùng.
Nhắc nhở. Trong thuật toán phân vùng, tất cả các phần tử được so sánh với phần tử trục và các phần tử nhỏ hơn trục được di chuyển về phía bên trái và phần tử lớn hơn được di chuyển về phía bên phải.
Bây giờ, vì mảng đã được chia thành hai phần, hãy bỏ qua một phần và chỉ cần tìm phần tử thứ N – K trong phần còn lại.
Hãy để chúng tôi hiểu điều này với một ví dụ.
thuật toán
- Chọn bất kỳ phần tử ngẫu nhiên nào của mảng làm trục
- Sử dụng thuật toán phân vùng để phân vùng mảng thành hai phần và đặt phần tử trục vào đúng vị trí của nó, idx
- Bây giờ, vì tất cả các phần tử ở bên trái của trục đều nhỏ hơn và ở bên phải của trục lớn hơn, hãy so sánh giá trị của idx với N – K và chọn đệ quy một phần của mảng để tìm phần tử lớn thứ K của mảng
Mã C++
Trong CPP, có một chức năng đảo ngược sẵn có trong tệp tiêu đề thuật toán, khi được truy cập có thể đảo ngược chuỗi/mảng