基地选拔测试的一个题 第k个数

Question

题目描述
给定一个 n×m 的方格矩阵，每个方格内都有一个整数元素。
其中第 i 行第 j 列的方格中的元素为 i×j（行和列都从 1 开始编号）。
现在，需要你将这 n×m 个整数按照非严格单调递增的顺序一一写出。
请问，你写出的第 k 个整数是多少。
输入描述:
一行，三个整数 n,m,k。
输出描述:
一行，输出你写出的第 k 个整数。
示例1
输入
复制
2 2 2
输出
复制
2
备注:
数据范围
1≤n,m≤5×105， 1≤k≤n×m 。

是基地招新测试的题，当时时间有点赶没什么思路就直接跳过了，有帮忙给点思路的吗？

Answer 1

二维数组可以用一维数组形式保存，用排序算法对数组排序后，输出a[k-1]就可以了
代码如下：

#include <stdio.h>
//冒泡排序
void bubble_sort(int a[],int n)
{
    int i,j,t;
    for (i=0;i<n-1;i++)
    {
        for (j=0;j<n-1-i;j++)
        {
            if(a[j] > a[j+1])  //从小到大，升序
            {
                t = a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}

int main()
{
    int a[5*105],i,j;
    int m,n,k;
    scanf("%d %d %d",&m,&n,&k);
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            a[i*n+j] = (i+1)*(j+1);
        }
    }
    bubble_sort(a,m*n);
    printf("%d",a[k-1]);
    return 0;
}