首页 > 试题广场 >

二维表第k大数

[编程题]二维表第k大数
  • 热度指数:3330 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在一块长为n,宽为m的场地上,有n✖️m个1✖️1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下

n = 3, m = 3
1   2   3
2   4   6
3   6   9

给出一个查询的值k,求出按照这个方式列举的的数中第k大的值v。
例如上面的例子里,
从大到小为(9, 6, 6, 4, 3, 3, 2, 2, 1)
k = 1, v = 9
k = 2, v = 6
k = 3, v = 6
...
k = 8, v = 2
k = 9, v = 1

输入描述:
只有一行是3个数n, m, k 表示场地的宽高和需要查询的k。使用空格隔开。


输出描述:
给出第k大的数的值。
示例1

输入

3 3 4

输出

4

备注:
【数据范围】
100%的数据
1 <= n, m <= 40000
1 <= k <= n * m
30%的数据
1 <= n, m <= 1000
置顶的二分查找思路的java版本,java版本里有一个比较隐晦的int溢出问题,会导致divide zero异常,或者只有90%AC(题目会提示出现数组越界等错误/或者只有90%AC
import java.util.*;
public class Main {
    public static void problem5_2020() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int left = 1;
        int right = m * n;
        k = m * n - k + 1;
        while (left < right) {
            // 注意int类型溢出问题!
            int mid = (int)(((long)left + right) / 2);
            // 求小于等于 mid 的数量
            int row = mid / m;
            int count = row * m;
            for (int i = row + 1; i <= n; i++) {
                count += mid / i;
            }
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        System.out.println(left);
    }

    public static void main(String[] args) {
        problem5_2020();
    }
}


编辑于 2020-08-14 11:24:43 回复(2)
def find(m,n,k):
    left=1
    right=m*n
    k = m*n-k+1
    while left<right:
        mid=(left+right)//2
        count=0
        row = mid//n
        count += row*n 
        for i in range(row+1, m+1):
            count += mid//i
        if count>=k:
            right=mid
        else:
            left=mid+1
    return left
s = input()
m,n,k = s.split(" ")
print(find(int(m),int(n),int(k)))


发表于 2021-01-06 10:49:36 回复(0)
✭头像
import sys
def findMNK(m, n, k):
    #M*N的矩阵,其数值范围在1到M*N之间,题目给出长为n,宽(高)为m,即矩阵为m行n列
    left, right = 1, m*n
    while left < right:#循环跳出条件为left==right,区间左闭右开寻找
        mid = (left+right)//2#二分取中间值
        #求N*M的矩阵中有cnt个元素小于等于mid
        #矩阵每一行的数据可以表示为[1*i,2*i,3*i,...n*i]
        cnt = 0
        #for i in range(1, m+1):
            #cnt += min(mid//i, n)
        #简化上续循环次数
        row = mid//n#根据矩阵的排列,可以直接求出前row行的数均小于mid
        cnt += row*n 
        for i in range(row+1, m+1):
            cnt += mid//i
        if cnt<k:
            left = mid+1
        else:
            # 对于cnt==k的情况,此时的mid可能不在二维表中,但是此时mid一定比正确答案大
            right = mid
    return left
ls = [int(i) for i in sys.stdin.readline().split()]
n, m, k = ls[0], ls[1], ls[2]
k = m*n-k+1#转化为求第m*n-k小的数
print(findMNK(m, n, k))



编辑于 2020-07-31 17:25:46 回复(10)
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();
        int l = 0;
        int h = M * N;
        //反向序号
        K = M * N - K + 1;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            // 假定以mid作为最大数的所在行curRow; 由矩阵的特点可知:
            // curRow的上一行所有的数都将小于mid,缩小查找范围
            int curRow = mid / M;
            // 同理,获取所在列curCol;
            int curCol = mid / N;
            int cnt = curRow * M + curCol * (N - curRow);
            // 剩下右下角一个小矩形
            for (int i = curRow + 1; i <= N; i++) {
                for (int j = curCol + 1; j <= M && (i * j <= mid); j++) {
                    cnt++;
                }
            }
            if (cnt >= K) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(l);
    }
}


发表于 2020-07-30 10:04:02 回复(5)
这道题我提交后显示“请检查是否存在数组越界等非法访问情况,case通过率为30.00%”,想问下大家我代码是哪里出了错误。我的思路是将这个n*m数组转换为一维数组,在进行排序,最后要输出的第k大的值就是一维数组下表为n*m-k的值,测试用例我没试出问题,大家能帮我找到哪里错了么
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int t = 0;
        int[][] arr = new int[n][m];
        int[] a = new int[n*m];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i-1][j-1] = i * j;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[t] = arr[i][j];
                t++;
            }
        }
        Arrays.sort(a);

        System.out.println(a[m*n-k]);
    }
}


发表于 2020-08-01 19:20:14 回复(10)
#include <algorithm>
#include <iostream>

using namespace std;
long long min_(long long m, long long n, long long num)
{
    long long count = 0;
    for (long long i = 1; i <= m; ++i){
        count += min(num / i, n);
    }
    return count;
}

long long TwoSort(long long m, long long n, long long k)
{
    long long l = 1, r = m * n, mid; //int 最大值,最小值,中间值
    while (l < r)
    {
        mid = (r + l)>>1;
        long long tmp = min_(m, n, mid);
        if (tmp <= k)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    return l;
}

int main()
{
    long long n, m, k; cin >> n >> m >> k;
    k = m * n - k;
    cout << TwoSort(m, n, k) << endl;
    return 0;
}

编辑于 2020-05-25 01:01:22 回复(3)
package main

import (
"fmt"
)

func main() {
	var n,m,k int
	fmt.Scan(&n,&m,&k)
	left,right:=1,m*n
	k=m*n-k 
	for left<right{ 
		mid:=(left+right)/2
		cnt:=0
		row:=mid/n 
		cnt+=row*n
		for i:=row+1;i<m+1;i++{
			cnt+=mid/i
		}
		if cnt<=k{
			left=mid+1
		}else{
			right=mid
		}
	}
	fmt.Println(left)
}
Golang版本
发表于 2021-03-06 00:57:20 回复(0)
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();

		int start = 1;
		int end = n * m;
		while (start < end) {
			// 中位数, 这里不写成 mid = (start + end) / 2, 是为了防止整型溢出
			int mid = start + (end - start) / 2;
			// 记录数组中比mid大的数值个数
			int cnt = 0;
			// 记录数组中刚好大于mid的整数值
			// 例如mid = 50时, 若数组中大于50的数中最小值为51, 则res = 51. 
			int res = n * m;
			// 大于mid的数, 其x必大于mid/m, 其y必大于mid/n
			for (int i = mid / m + 1; i <= n; i++)
				for (int j = mid / n + 1; j <= m ; j++)
					// 找到第一个满足条件的数后, 直接将该列后续所有数字加进来, 减少复杂度, 非常重要!!!!
					if (i * j > mid) {
						cnt += (m - j + 1);
						if (res > i * j)
							res = i * j;
						// 这里的break只能跳出最内层的for循环
						break;
					}

			if (cnt > k)
				start = mid + 1;
			else if (cnt == k) {
				// 当cnt == k时, 直接取res即可
				start = res;
				break;
			} else if (cnt < k)
				// 这里不能令end = mid -1,否则有可能将最优解滤除
				// 假设大于50的数有19个, 等于50的数有3个, 此时cnt = 19, 若k = 20,
				// 最优解应为50, 故不能令end = mid -1
				end = mid;
		}
		System.out.println(start);
	}
}


编辑于 2020-10-21 22:17:41 回复(0)
#include<bits/stdc++.h>
using namespace std;
int CompareK(int n,int m,int mid)
{
    long result = 0;
    int col = m;//最后一列,为最大数字
    int row = 1;//第一行
    while(col >0 && row <= n)
    {
        if(col*row <= mid)
        {
            result += col;//这里会随着col--减小之后,col*row会再次小于mid,这时会继续加上col,所以result可能特别大
            row++;//中间值在当前行的下面
        }
        else
            col--;//当col*row>mid时col--,说明中间值在最后一列的左边
    }
    return result;
}
int FindK(int n,int m,int k)
{
    int left = 1;
    long right = n*m;
    while(left < right)
    {
        int mid = left + (right-left)/2;
        if(CompareK(n,m,mid) >= k)
            right = mid;
        else
            left = mid+1;
    }
    return left;
}
int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    int result = FindK(n,m,k);
    cout << result << endl;
    return 0;
}
从leetcode上看的,到这里就不行,有哪位大佬解决一下。

发表于 2020-08-14 22:43:33 回复(0)

闲的无聊试了一下优先队列解法,发现只通过60%,蹲一个大佬解惑

#include<iostream> #include<queue> #include<vector> using namespace std; class Node{ public:     long x,y;     Node(long a,long b):x(a),y(b){} }; bool operator <(Node a,Node b){     if(a.y == b.y) return a.x<b.x;     return a.y<b.y; } int main(){     long n,m,k;     cin>>n>>m>>k;     priority_queue<Node>pq;     for(int i=1;i<=m;i++){         pq.push(Node(i,i*m));     }     int ans = 0;     while(k--){         int row=pq.top().x;         int val=pq.top().y;         ans =val;         pq.pop();         val-=row;         if(val>0)             pq.push(Node(row,val));     }     cout<<ans<<endl;     return 0;

发表于 2020-08-01 16:50:25 回复(1)
🤣🤣🤣
发表于 2020-08-01 11:17:18 回复(0)
public int getNum(int n,int m,int k){
    return  integerList(n,m).get(k); }  public List<Integer> integerList(int n,int m){
    List<Integer> list = new ArrayList<>(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){
            list.add(i*j);
        }
    }
    list.sort(new Comparator<Integer>() { @Override  public int compare(Integer o1, Integer o2) { return o2-o1;
        }
    }); return list;
}

发表于 2020-06-23 10:58:53 回复(0)
function findIndex(n,m,k){
var gridArr = [];
for (var i = 1; i < n + 1; i++) {
for (var j = 1; j < m + 1; j++) {
gridArr.push(i * j);
}
}
gridArr.sort(function (a, b) {
return b - a;
});
console.log("单元格排列数字是:"+gridArr);
console.log("第k大的值是:"+gridArr[k-1]);
return gridArr[k-1];
}
findIndex(5,5,5)
发表于 2020-05-21 10:42:34 回复(0)