c – 查找数组的子数组,其数量除以给定数字

发布时间：2020-12-16 06:47:10 所属栏目：百科来源：网络整理

导读：我遇到了一个算法问题.请为我提出一些针对以下问题的有效算法. 问题是查找数量的子数组,其总和可以被给定的数字整除. 我的工作我做了一个算法,其复杂度为O(N ^ 2),这里,N =数组的大小. 我的守则 #includestdio.husing namespace std; main() { int N; int

我遇到了一个算法问题.请为我提出一些针对以下问题的有效算法.

问题是

查找数量的子数组,其总和可以被给定的数字整除.

我的工作

我做了一个算法,其复杂度为O(N ^ 2),这里,N =数组的大小.

我的守则

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d",&T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d",&N);
        scanf("%d",&P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d",&val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%dn%lldn",k,answer);
    }
    return 0;
 }

解决方法

对于给定的数字X ……

基本思路:(具有正确性的非正式证明)

如果[a,b]范围内的数字之和可被X整除,则：

(Σi= 1到a-1input [i])％X =(Σi= 1到binput [i])％X

用较少的数学术语：

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

所以：

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

然后,如果右边的那些总和在除以X时都具有相同的余数,则剩余部分将抵消,并且两者之间的元素之和将被X整除.详细说明：

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

现在我们可以将B转换为形式PX Q和A形式为RX S形式,对于某些整数P,Q,R和S,其中0 <= Q,S< X.这里,根据定义,Q和S将是B和A的相应余数除以X. 然后我们有：

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

显然(P-R)X可以被X整除(结果就是(P-R)).现在我们只需要Q-S可以被X整除,但是,因为0 <= Q,S< X,他们需要平等. 例：设B = 13,A = 7,X = 3. 这里B％X = 1且A％X = 1. 我们可以将B重写为4 * 3 1,将A重写为2 * 3 1. 然后C = 4 * 3 1 – 2 * 3 – 1 = 2 * 3,可被3整除. 高级方法：构造密钥的哈希映射 – > value,其中每个值表示从数组的开头可以开始的方式,并在某个给定位置结束,加起来为sum mod X = key(请参阅下面示例中的“Mod 3”行和地图值) ).

现在,基于上面的逻辑,我们知道如果两个子阵列从开始开始并分别在位置a和b结束,两者具有相同的和模x,则子阵列[a,b]将被X整除.

因此,散列图中的每个值表示一组可能的起点和终点的大小,这将给我们一个可被X整除的子阵列(任何点都可以是起点或终点).

选择这些起点和终点的可能方式很简单
value choose 2 = value!/(2*(value-2)!)(如果值为1则为0).

因此,我们计算哈希映射中的每个值并将它们全部加起来以获得可被X整除的子数组的数量.

算法：

构造一个哈希映射,它将存储到目前为止所有数字的累积和,映射到该剩余值出现的频率计数(在预期的O(n)中构造).

将0的值增加1 – 这对应于数组的开始.

将计数初始化为0.

对于散列映射中的每个值,将值！/(2 *(value-2)！)添加到计数中.

计数是期望值.

运行时间：

预期O(n).

例：

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

子阵列将是：

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!