C语言 子阵列中的内存限制超出问题

k2arahey  于 2023-06-05  发布在  其他
关注(0)|答案(1)|浏览(145)

我在试着解决一个问题,但是我的记忆力已经超过了极限。
问题描述
给定一个整数数组A和两个整数B和C。
你需要找出B出现的次数等于C出现的次数的子数组的个数。
注意:不要计算空的子数组。
输入格式第一个参数是整数数组A。
第二个参数是整数B。
第三个参数是整数C。
输出格式返回一个整数,表示B出现的次数等于C出现的次数的子数组的数量。

/**
 * @input A : Integer array
 * @input n1 : Integer array's ( A ) length
 * @input B : Integer
 * @input C : Integer
 * 
 * @Output Integer
 */
int SubArrays(int* arr, int start, int end, int size, int B, int C)
{
   
    int countB = 0,countC = 0;
    // Stop if we have reached the end of the array
    if (end == size)
        return 0;
    
    // Increment the end point and start from 0
    else if (start > end)
        SubArrays(arr, 0, end + 1, size, B, C);
   
    // Print the subarray and increment the starting point
    else {
        int A[end-start+1];
        int i, j;
        for ( i = start; i < end; i++){
            for(j =0; j<(end-start+1);j++){
                A[j] = arr[i];
            }
        }
        for(j =0; j<(end-start+1);j++){
            if(A[j]==B) countB ++;
            if(A[j]==C) countC ++;
        }
        // cout << arr[end] << "]" << endl;
        SubArrays(arr, start + 1, end, size, B, C);
    }
    if(countB == countC)
        return 1;
    else
        return 0;
}
int solve(int* A, int n1, int B, int C) {
    int count = 0;
    count = count + SubArrays(A,0,0,n1,B,C);
    return count;
}
ndasle7k

ndasle7k1#

在一般情况下,您的例程创建一个数组int A[end-start+1],然后递归地调用它自己。这会占用很多空间,而且没有必要。
许多挑战或在线评判问题旨在创造性地解决,使用问题的“更大”视图,而不是“蛮力”,例如检查所有可能的组合。
在这种情况下,解决方案是:

  • 创建辅助数组T,并将每个元素Ti 设置为 BA 的从A0到Ai 的元素中出现的次数减去 CA 的从A0到Ai 的元素中出现的次数,包括A0和A * i *。例如,B = 3,C = 4,A如下所示:

| * 我 *| 0| 1| 2| 3| 4| 5个|六|七个|八|
| - -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|
| 一个|1| 3| 3| 5个|4| 0| 4| 4| 4|
| T型|0| +1| +2| +2| +1| +1| 0| −1| −2|

  • 然后使用T查找子数组。对于使得Ti = Tj 的任何 ij,A的从Ai 到Aj(包括A * i * 和A * j *)的子阵列将包含相等数量的 B 值和 C 值。
  • 您可以通过简单地迭代所有 ij 值来计算这些值,其中 ij

例如,利用上述,(0,6)(意味着 i=0,j=6)形成具有相等数量的 B 值和 C 值的子阵列,并且(1,4)、(1,5)、(2,3)和(4,5)也是如此。因此,所需的子阵列数量为5。
(If如果允许修改原始数组,则可以在数组中就地计算该辅助信息,替换其原始内容。
这将给予你一个解决方案,所需时间大致与 n2成正比,其中 n 是A中元素的数量。但是,有一个更好的解决方案:

  • 排序 T。这将把所有相同的值放在一起。然后,您可以迭代 T,并轻松计算每个值出现的次数。对于出现 m 次的值,可以由它形成 m·(m−1)/2对 ij 值,因此将 m·(m−1)/2添加到运行总数。在遍历T结束时,total是所需的子数组数量。

这给出了一个运行时间大致与 n log n 成比例的解决方案。
它可以在一个函数中实现,其中包含七行C代码(利用一些有经验的程序员可能使用的C符号,但合理)和一个辅助函数(用于排序比较),只有一行或两行。
计数对的提示:您不需要等到重复序列结束才添加到运行总数中。如果T中的当前值到目前为止已经出现了 m 次,则将 m−1添加到运行总数中。当该值被看到 m 次时,将为它们添加 m·(m−1)。例如,如果一个值被看到四次,我们将在第一次看到它时添加0,然后是1,然后是2,然后是3,1+2+3 = 4·(4−1)/2。

相关问题