找到数组中最长的连续体，连续体中的值之和等于零模3 [英] Find the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3

问题描述

我写了一个代码，找到数组中最长的连续体，连续体中的值之和等于零模3，例如对于数组 a [] = {2，-3， 5,7，-20,7}

我们有2-3 + 5 + 7-20 = -9，所以输出为5 ，我的问题是的复杂性，现在是 O（n ^ 3）一只鸟低声说，可以在 O（n）

  public class mmn {
 public static void main [] args）
 {
 int a [] = {2，-3,5,7，-20,7}; 
 int r = what（a）; 
 System.out.println（r）; 
} 
 private static int f（int [] a，int low，int high）
 {
 int res = 0; （int i = low; i< = high; i ++）
 res + = a [i]; 
 
 return res; 
} 
 public static int what（int [] a）
 {
 int temp = 0; （int i = 0; i  {
 for（int j = i; j< a.length; j ++）
 {
 int c = f（a，i，j）; 
 if（c％3 == 0）
 {
 if（j-i + 1> temp）
 temp = j-i + 1; 
} 
} 
} 
 return temp; 
} 
 
} 
  

尝试重写O（n）：

  import java.util。*; 
 class Main {
 public static void main（String [] args）throws Exception {
 //应该只使用一个Scanner对象
扫描仪扫描器=新的扫描仪（System.in ）; 
 int a [] = {3,1,3,1,3,1}; 
 int n = a.length; 
 int S [] = new int [n]; 
 int i [] = new int [n]; 
 int最好; 
 int sum; （int j = 0; j< n; j ++）
 
 {
 S [j] = a [j]％3; 
 i [j] = j; //初始化
 //System.out.println(S[j]）; 
 //System.out.println(i[j]）; 
} 
 best = 1; （int k = 1; k  if（（S [k-1] + S [k]）％3 == 0）{//检查是否需要更长的连​​续体
 S [k] = S [k-1] + a [k]; 
 i [k] = i [k-1]; 
} 
 if（S [k]< S [best]）//检查我是否应该更新更好的
 best = k-1; 
} 
 System.out.println（best）; 
} 
} 
  

解决方案

在Python中的一个 O（n）算法的例证，使一个遍历数组。这个想法是 dp [i] [r] 表示最长的序列， s ，以索引 i 其中（sum s）％3 = r 。 Cleary我们寻找最高的 dp [i] [0] 。如果前面的步骤根据适当的模结果记录任何长度，我们只能增加特定单元的序列。由于我们每次通过数组迭代访问三个单元格（一个常量），所以该算法具有时间和空间复杂度。 （空格可以很容易地适应 O（1），因为我们只需要在每次迭代时使用前三个单元格。）

< pre class =lang-py prettyprint-override> a = [2，-3,5,7，-20,7]

best = 0
对于我在范围（1（1）+ 1）中的i，bestIndex = -1

dp = [[0,0,0]]]

len（a）+ 1）：
r = a [i-1]％3

为范围（3）中的j：
canSumToJ = dp [i-1] [ （3 + j-r）％3]> 0

dp [i] [j] = max（1如果r == j else 0
，1 + dp [i-1] [（3 + j - r）％3 ]如果canSumToJ else 0）

bestIndex = i - 1如果dp [i] [0]>最佳其他bestIndex
best = max（best，dp [i] [0]）

print（best，（bestIndex - best + 1，bestIndex））＃（5，（0， 4））

＃dp
＃=> [[0，0，0]
＃，[0，0，1]
＃，[1，0，2]
＃，[0,3,2]
＃，[3，1，4]
＃，[5，4，2]
＃，[3，6，5]]
pre>

I wrote a code that finds the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3, e.g for the array a[]={2,-3,5,7,-20,7}

We have 2-3+5+7-20=-9 so the output is 5, My problem is the complexity, now it's O(n^3) a bird whispered me that it can be done in O(n)

public class mmn {
public static void main(String[] args)
{
    int a[]={2,-3,5,7,-20,7};
    int r=what(a);
    System.out.println(r);
}
private static int f(int[]a,int low, int high)
{
int res=0;
for (int i=low;i<=high;i++)
    res+=a[i];
return res;
}
    public static int what(int[]a)
    {
    int temp=0;
    for(int i=0;i<a.length;i++)
    {
        for (int j=i;j<a.length;j++)
        {
            int c=f(a,i,j);
            if (c%3==0)
            {
                if(j-i+1>temp)
                    temp=j-i+1;
            }
        }
    }
    return temp;
    }

}

Attempt to rewrite in O(n):

import java.util.*;
class Main {
public static void main (String[] args) throws Exception {
// you should use only one Scanner object
Scanner scanner = new Scanner(System.in);
int a[]={3,1,3,1,3,1};
int n=a.length;
int S[]=new int[n];
int i[]=new int[n];
int best;
int sum;

for (int j=0; j<n; j++) {
    S[j]=a[j]%3;
    i[j]=j;// initialize
    //System.out.println(S[j]);
    //System.out.println(i[j]);     
}
best=1;
for (int k=1; k<n; k++) {
    if((S[k-1]+S[k])%3==0) {//checking if we want a longer continuum
        S[k]=S[k-1]+a[k];
        i[k]=i[k-1];
    }    
    if(S[k]<S[best])//check if i should update the better
        best=k-1;
    }
    System.out.println(best);
}
}

解决方案

Here's an illustration of an O(n) algorithm in Python, making one pass over the array. The idea is that dp[i][r] represents the longest sequence, s, ending at index i where (sum s) % 3 = r. Cleary we look for the highest dp[i][0]. We can only augment the sequence for a particular cell if the previous step recorded any length at all for the appropriate modulo result. Since we access only three cells (a constant) on each iteration through the array, the algorithm has O(n) time and space complexity. (Space can be easily adapted to O(1) since we only need the previous three cells at each iteration.)

a = [2,-3,5,7,-20,7]

best = 0
bestIndex = -1

dp = [[0,0,0] for i in range(len(a) + 1)]

for i in range(1,len(a) + 1):
  r = a[i-1] % 3

  for j in range(3):
    canSumToJ = dp[i-1][(3 + j - r) % 3] > 0

    dp[i][j] = max(1 if r == j else 0
                  ,1 + dp[i-1][(3 + j - r) % 3] if canSumToJ else 0)

  bestIndex = i - 1 if dp[i][0] > best else bestIndex
  best = max(best,dp[i][0])

print(best,(bestIndex - best + 1, bestIndex)) # (5, (0, 4))

# dp
# => [[0, 0, 0]
#    ,[0, 0, 1]
#    ,[1, 0, 2]
#    ,[0, 3, 2]
#    ,[3, 1, 4]
#    ,[5, 4, 2]
#    ,[3, 6, 5]]

这篇关于找到数组中最长的连续体，连续体中的值之和等于零模3的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！