如果我有一个乘法表，比如3x5大小的：
尝试克服内存限制，我尝试按顺序计算每个数字的出现次数，直到中间位置。我注意到，每个数字在乘法表中出现的次数等于它们拥有的因子数量。
速度还不够快。
有人可以提供任何指针吗？我知道在建议的 O(N log NM) 解决方案中使用了二分查找。
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;
}
}
}
}
尝试克服内存限制，我尝试按顺序计算每个数字的出现次数，直到中间位置。我注意到，每个数字在乘法表中出现的次数等于它们拥有的因子数量。
速度还不够快。
有人可以提供任何指针吗？我知道在建议的 O(N log NM) 解决方案中使用了二分查找。
1 <= N <= 10^5
1 <= M <= 10^5
解决方案！
好的，感谢@PeterdeRivaz的帮助，我成功地找到并实现了解决我的问题的方法。这个想法就像他所描述的那样，下面是实际的实现：
public class Kertotaulu {
public static void main(String[] ar) { Scanner scanner = new Scanner(System.in); long h = scanner.nextLong(); long w = scanner.nextLong();
long min = 1; long max = w*h; long mid = 0; while (min <= max) { mid = (min + max) / 2; long sum = 0; for (int i = 1; i <= h; i++) sum += Math.min(mid / i, w); sum--;
if (sum < (w * h) / 2) min = mid + 1; else if (sum > (w * h) / 2) max = mid - 1; else break; }
long sum = 0; for (int i = 1; i <= h; i++) sum += Math.min((mid - 1) / i, w); sum--;
if (sum == (w * h) / 2) System.out.println(mid - 1); else System.out.println(mid); }
}