爪哇：2D陣列的總和，其中所述M [i] [j] =（int）的I/J，

筆 - 測試用例數| 1 < = T < = 10和n - 元素的數量| 1 < = N < = 1000000爪哇：2D陣列的總和，其中所述M [i] [j] =（int）的I/J，

例如

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

來源

2017-04-26 iamvroon

I> = 1且j> = 1。 – iamvroon

這裏很明顯，你不需要將值存儲在矩陣，因爲它是不可能有那麼大的空間（Array[10000][10000]）來分配。所以你需要用mathematical的方式來思考。

考慮一個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

通過將其分成列解決這個矩陣和解決每個columns的。對於第一列系列將1+2+3+4。然後對列號two(2)系列將0+1+1+2。

請注意，對於ith列firsti-1值爲零，然後i values在列中相同。然後value增加。 i值也是一樣。再次增加1等。

所以在ith列值獲得increased的jth元素，其中j%i==0上。

所以你可以在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); 
     } 
    } 
}

來源

2017-04-26 06:11:09

謝謝Sanket。實際上是在思考同一條線。得到了我正在尋找的答案。 – iamvroon

爪哇：2D陣列的總和，其中所述M [i] [j] =（int）的I/J，

回答

相關問題