Số nhỏ nhất thứ K trong bảng cửu chương trong C ++

Giả sử chúng ta biết về một Bảng Nhân. Nhưng liệu chúng ta có thể tìm ra số nhỏ thứ k một cách nhanh chóng từ bảng cửu chương không? Vì vậy, nếu chúng ta có chiều cao m và chiều dài n của một Bảng nhân m * n và một số nguyên dương k, chúng ta phải tìm số nhỏ nhất thứ k trong bảng này.

Vì vậy, nếu m =3 và n =3 và k là 6, thì kết quả sẽ là 4., điều này là do bảng cửu chương giống như -

Phần tử nhỏ thứ 6 là 4 as [1,2,2,3,3,4,6,6,9]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm ok (), điều này sẽ lấy m, n, x,
• ret:=0
• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
  • temp:=tối thiểu là x / i và m
  • ret:=ret + temp
• trả lời lại
• Từ phương pháp chính, hãy thực hiện như sau -
• ret:=-1, low:=1, high:=m * n
• while low <=high, do -
  • giữa:=low + (cao - thấp) / 2
  • cnt:=ok (m, n, mid)
  • nếu cnt> =k, thì -
    • cao:=giữa - 1
    • ret:=mid
  • Mặt khác
    • thấp:=giữa + 1
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ok(int m, int n, int x){
      int ret = 0;
      for(int i = 1; i <= n; i++){
         int temp = min(x / i, m);
         ret += temp;
      }
      return ret;
   }
   int findKthNumber(int m, int n, int k) {
      int ret = -1;
      int low = 1;
      int high = m * n ;
      while(low <= high){
         int mid = low + (high - low)/ 2;
         int cnt = ok(m, n, mid);
         if(cnt >= k){
            high = mid - 1;
            ret = mid;
         }else low = mid + 1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findKthNumber(3,3,6));
}

Đầu vào

“2*”

Đầu ra

4