พิจารณาว่าเรามีอาร์เรย์ A และอีกสองจำนวนเต็ม K และ M เราต้องหาองค์ประกอบที่ K-th น้อยที่สุดหลังจากต่ออาร์เรย์กับตัวมันเอง M ครั้ง สมมติว่าอาร์เรย์เป็น A = [3, 1, 2], K = 4 และ M = 3 หลังจากต่อ A 3 ครั้ง จะได้ [3, 1, 2, 3, 1, 2, 3, 1, 2] องค์ประกอบที่ 4 ที่น้อยที่สุดคือ 2
เพื่อแก้ปัญหานี้ เราจะเรียงลำดับอาร์เรย์ A แล้วคืนค่าที่อยู่ที่ดัชนี ((K - 1)/M) ของอาร์เรย์
ตัวอย่างโค้ด C++
#include <iostream>
#include <algorithm>
using namespace std;
int findKSmallestNumber(int A[], int N, int M, int K) {
sort(A, A + N);
return (A[((K - 1) / M)]);
}
int main() {
int A[] = { 3, 1, 2 };
int M = 3, K = 4;
int N = sizeof(A) / sizeof(A[0]);
cout << K << "th smallest number after concatenating " << M << " times, is: " << findKSmallestNumber(A, N, M, K);
}
ผลลัพธ์
4th smallest number after concatenating 3 times, is: 2
