T - 测试用例数量 | 1<=T<=10 且 n - 元素数量 | 1<=n<=1000000
例如
if (T >= 1 && T <= 10) {
for (int i = 0; i < T; i++) {
int n = sc.nextInt();
if (n > 0 && n <= 1000000) {
array = new int[n][n];
System.out.print("\n" + sumOfArray(array, n));
}
}
}
需要求M[i][j]的和,其中M[i][j] = (int) i/j;
我已经编写了代码,但是对于 n>10000,我开始出现 OOM(出于明显的原因)。
如果有人能帮助我,那就太好了。需要一种全新的方法来解决问题。
例如。
Input Output
2
2 4
4 17
最佳答案
很明显,您不需要将值存储在矩阵中,因为不可能有那么多空间 (Array[10000][10000]
) 可供分配。所以你需要以数学
的方式思考。
考虑一个 4x4
矩阵并用 i,j
项表示每个元素。
1,1 1,2 1,3 1,4
2,1 2,2 2,3 2,4
3,1 3,2 3,3 3,4
4,1 4,2 4,3 4,4
现在我们可以在这里表示每个元素中存储的内容。
1/1 1/2 1/3 1/4 (In Integers) 1 0 0 0
2/1 2/2 2/3 2/4 ============> 2 1 0 0
3/1 3/2 3/3 3/4 3 1 1 0
4/1 4/2 4/3 4/4 4 2 1 1
通过将其划分为列来处理该矩阵并求解每个列
。
对于第一列系列将为 1+2+3+4
。然后对于列号 two(2)
,该系列将为 0+1+1 +2
。
请注意,对于第 i
列,first
i-1
值为零,然后 i 值
相同在专栏中。然后值
就会增加。同样,i
值也是相同的。再次增加1
,依此类推。
因此,在第 i 个列中,第 j%i==0 元素的第 j 个元素的值增加了。
因此,您可以在 1-D
数组中实现此逻辑,并且对于每个测试用例,此方法的复杂性将为 O(n logn)
。
代码:
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int testcases=sc.nextInt();
while(testcases-- >0)
{
int n=sc.nextInt();
long array[]=new long[n+1]; //Take long array to avoid overflow
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j+=i)
{
array[j]++; //This will store that which elements get increased
//from zero how many times
}
}
//Now we can do summation of all elements of array but we need to do prefix sum here
long sum=0;
for(int i=1;i<=n;i++)
{
array[i]+=array[i-1];
sum+=array[i];
}
System.out.println(sum);
}
}
}
关于Java:二维数组的总和,其中 M[i][j] = (int) i/j,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43625853/