สมมติว่าเรารู้ตารางสูตรคูณหนึ่ง แต่เราสามารถหาจำนวนที่น้อยที่สุดที่ k จากตารางสูตรคูณได้หรือไม่? ดังนั้นหากเราต้องสูง m และความยาว n ของตารางคูณ m * n และจำนวนเต็มบวก k หนึ่งตัว เราต้องหาจำนวนที่น้อยที่สุดที่ k ในตารางนี้
ดังนั้นถ้า m =3 และ n =3 และ k เป็น 6 ผลลัพธ์จะเป็น 4 นั่นเป็นเพราะตารางสูตรคูณเป็นแบบนี้ -
| | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 |
| 2 | 2 | 4 | 6 |
| 3 | 3 | 6 | 9 |
องค์ประกอบที่เล็กที่สุดที่ 6 คือ 4 เป็น [1,2,2,3,3,4,6,6,9]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน ok() ซึ่งจะใช้เวลา m, n, x,
- ret :=0
- สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- อุณหภูมิ :=ต่ำสุด x / i และ m
- ret :=ret + อุณหภูมิ
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ret :=-1, ต่ำ :=1, สูง :=m * n
- ในขณะที่ต่ำ <=สูง ทำ −
- กลาง :=ต่ำ + (สูง - ต่ำ) / 2
- cnt :=ok(m, n, mid)
- ถ้า cnt>=k แล้ว −
- สูง :=กลาง - 1
- ret :=กลาง
- มิฉะนั้น
- ต่ำ :=กลาง + 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
“2*”
ผลลัพธ์
4
