Leetcode 668. 乘法表中第k小的数（DAY 190）---- 二分查找学习期

Myth丶恋晨 2022-09-16 04:46 144阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷超时 TLE 优先队列 59/70）
     *  代码实现（首刷 看了思路 二分优化）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷超时 TLE 优先队列 59/70） ##

--------------------

class Solution { 
    public:
        int findKthNumber(int m, int n, int k) { 
            struct node
            { 
                int val,x,y;
                node(int val,int x,int y):val(val),x(x),y(y){ }
                bool operator > (const node& b) const { return val > b.val;} 
            };
            vector<vector<int>> cnt(m,vector<int>(n,0));
            for(int i=1;i<=n;++i)   cnt[0][i-1] = i;
            for(int i=1;i<m;++i)
                for(int j=0;j<n;++j)
                    cnt[i][j] = cnt[0][j] *(i+1);
            priority_queue<node,vector<node>,greater<node>> q;
    
            for(int i=0;i<cnt.size();++i)
                q.emplace(cnt[i][0],i,0);
                
            while(--k)
            { 
                auto x = q.top().x,y = q.top().y;
                q.pop();
                if(y != n-1)    q.emplace(cnt[x][y+1],x,y+1);
            }
            return q.top().val;
        }
    };

--------------------

## 代码实现（首刷 看了思路 二分优化） ##

--------------------

class Solution { 
    public:
        int above_k(int m,int n,int mid,int k)
        { 
            int lower_num = 0;
            for(int i=1;i<=min(mid,m);++i)
                lower_num += min(mid/i,n);  
            return lower_num >= k;
        }
    
        int findKthNumber(int m, int n, int k) { 
            int left = 1,right = m*n;
            while(left < right)
            { 
                int mid = (left + right)/2;
                if(above_k(m,n,mid,k))  right = mid;
                else left = mid+1;
            }
            return left;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/00b14165d14048a69e05032cfae403c6.png