如果一个NxM的乘法table按顺序排列，中间的数是多少？

Question

如果我有一个 table 大小的乘法，例如 3x5:

1  2  3  4  5
2  4  6  8 10
3  6  9 12 15

然后我将所有这些数字排序：

1 2 2 3 3 4 4 5 6 6 8 9 10 12 15

中间的数字是多少？在本例中，它是 5.

N和M总是奇数，所以只能有一个答案。

有没有快速解决的办法？我正在寻找 O(N log NM)

中的内容

这是某种家庭作业，但我真的迷失在这个作业中。我想出了一些想法，但它们都有一些缺点：

public class Table {

    public static void main(String[] ar) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();

        int[] s = new int[w * h + 1];
        for (int i = 1; i <= w; i++)
            for (int j = 1; j <= h; j++)
                s[i * j] = s[i * j] + 1;

        int sum = 0;
        for (int i = 0; i < s.length; i++) {
            sum += s[i];
            if (sum >= s.length / 2) {
                System.out.println(i);
                break;
            }
        }
    }

}

这解决了大部分测试足够快（<4s），但是对于大 N 和 M，内存限制被超过（我不知道确切的限制）。

想法是跟踪每个数字的出现次数，然后按顺序遍历所有数字，每次迭代添加出现次数。当出现次数大于或等于w * h / 2时，就是中间的数，我们打印出来

public class Table {

    public static void main(String[] ar) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();

        int sum = 0;
        for (int i = 1; i <= w * h; i++) {
            for (int j = 1; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    int k = i / j;
                    if (k <= w && k != j) sum++;
                    if (k <= h && k != j) sum++;
                    if (k <= w && k <= h && k == j) sum++;
                }                
            }

            if (sum >= (w * h + 1) / 2) {
                System.out.println(i);
                break;
            }
        }
    }

}

为了克服内存限制，我尝试计算每个数字出现的次数，直到出现中间一个为止。我注意到每个数字的乘法 table 中出现的次数是它们具有的因子数。

不够快。

谁能指点一下？我知道在建议的 O(N log NM) 解决方案中使用了二进制搜索。

1 <= N <= 10^5
1 <= M <= 10^5

解决方法！

好的，感谢@PeterdeRivaz，我能够找到并实施解决我的问题的方法。这个想法正如他所描述的那样，这是实际的实现：

    public class 克托陶鲁 {


        public static void main(String[] ar) {
            扫描仪扫描仪=新扫描仪（System.in）；
            长 h = scanner.nextLong();
            长 w = scanner.nextLong();


            长分钟 = 1;
            最大长 = w*h；
            长中 = 0;
            而（最小<=最大）{
                中间 = (最小 + 最大) / 2;
                长和= 0；
                for (int i = 1; i <= h; i++) sum += Math.min(mid / i, w);
                和 - ;


                如果（总和<（w * h）/ 2）min = mid + 1；
                否则如果（总和>（w * h）/ 2）max = mid - 1；
                否则中断；
            }


            长和= 0；
            对于 (int i = 1; i <= h; i++) sum += Math.min((mid - 1) / i, w);
            和 - ;


            如果 (sum == (w * h) / 2) System.out.println(mid - 1);
            否则 System.out.println(中);
        }


    }

Answer 1

您可以通过计算乘法 table 中有多少条目小于该值来对值使用二进制搜索。

这将需要在二进制搜索中进行 log(NM) 次迭代，因此我们需要能够计算 O(N) 中的计数，总复杂度为 O(Nlog(NM))。

这可以通过依次考虑每个乘法 table 来完成。例如，假设我们的测试值为 8，我们正在考虑 3 次 table.

小于8的值将是3*1和3*2。我们可以通过简单地将测试值 8 除以 table 3 并向下舍入来找到有多少，即 floor(8/3) = 2 所以 3 次 table 会给我们一个计数2.

如果一个NxM的乘法table按顺序排列，中间的数是多少？

If an NxM multiplication table is put in order, what is number in the middle?

java

algorithm

binary-search

解决方法！