Phần tử K-th của hai mảng đã sắp xếp trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm phần tử thứ K từ mảng gộp của hai mảng đã sắp xếp.

Các bước giải quyết

• Khởi tạo hai mảng đã sắp xếp.
• Khởi tạo mảng rỗng kích thước M + N.
• Gộp hai mảng vào mảng mới.
• Trả về phần tử K - 1 từ mảng gộp.

Ví dụ

Dưới đây là mã nguồn C++:

#include <iostream> 
using namespace std; 

int findKthElement(int arr_one[], int arr_two[], int m, int n, int k) { 
    int sorted_arr[m + n]; 
    int i = 0, j = 0, index = 0; 
    while (i < m && j < n) { 
        if (arr_one[i] < arr_two[j]) { 
            sorted_arr[index++] = arr_one[i++]; 
        } else { 
            sorted_arr[index++] = arr_two[j++]; 
        } 
    } 
    while (i < m) { 
        sorted_arr[index++] = arr_one[i++]; 
    } 
    while (j < n) { 
        sorted_arr[index++] = arr_two[j++]; 
    } 
    return sorted_arr[k - 1]; 
} 

int main() { 
    int arr_one[5] = {1, 3, 5, 7, 9}, arr_two[5] = {2, 4, 6, 8, 10}; 
    int k = 7; 
    cout << findKthElement(arr_one, arr_two, 5, 4, k) << endl; 
    return 0; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

7

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.