資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中乘法表中的第 K 小數
假設我們知道一個乘法表。但是我們能否快速找到乘法表中的第 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
- for i := 1 to n do −
- temp := min(x / i, m)
- ret := ret + temp
- return ret
- 在主方法中，執行以下操作：
- ret := -1, low := 1, high := m * n
- while low <= high do −
- mid := low + (high - low) / 2
- cnt := ok(m, n, mid)
- if cnt >= k then −
- high := mid - 1
- ret := mid
- 否則
- low := mid + 1
- return ret
讓我們看下面的實現來更好地理解：
示例
#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
更新於：2020年6月1日
268 次瀏覽
廣告