用于寻找最大平衡子阵列的节省空间的算法？

Question

给定0和1的数组,找到最大子阵列,使得零和1的数量相等.这需要在O(n)时间和O(1)空间中完成.

我有一个算法在O(n)时间和O(n)空间中进行.它使用前缀和数组,并利用如果0和1的数量相同的事实,则sumOfSubarray = lengthOfSubarray/2

#include<iostream>
#define M 15

using namespace std;

void getSum(int arr[],int prefixsum[],int size) {
    int i;
    prefixsum[0]=arr[0]=0;
    prefixsum[1]=arr[1];
    for (i=2;i<=size;i++) {
        prefixsum[i]=prefixsum[i-1]+arr[i];
    }
}

void find(int a[],int &start,int &end) {
    while(start < end) {
        int mid = (start +end )/2;
        if((end-start+1) == 2 * (a[end] - a[start-1]))
                break;
        if((end-start+1) > 2 * (a[end] - a[start-1])) {
            if(a[start]==0 && a[end]==1)
                    start++; else
                    end--;
        } else {
            if(a[start]==1 && a[end]==0)
                    start++; else
                    end--;
        }
    }
}

int main() {
    int size,arr[M],ps[M],start=1,end,width;
    ;
    cin>>size;
    arr[0]=0;
    end=size;
    for (int i=1;i<=size;i++)
            cin>>arr[i];
    getSum(arr,ps,size);
    find(ps,start,end);
    if(start!=end)
            cout<<(start-1)<<" "<<(end-1)<<endl; else cout<<"No soln\n";
    return 0;
}

Answer 1

现在我的算法是O(n)时间和O(Dn)空间,其中Dn是列表中的总体不平衡.

此解决方案不会修改列表.

设D是列表中找到的1和0的差值.

首先,让我们在列表中线性地计算并计算D,只是为了看看它是如何工作的:

我将以此列表为例:l = 1100111100001110

Element   D
null      0
1         1
1         2   <-
0         1
0         0
1         1
1         2
1         3
1         4
0         3
0         2
0         1
0         0
1         1
1         2
1         3
0         2   <-

找到最长的平衡子阵列相当于在D中找到2个相等的元素,这是更远的appart.(在本例中,标有箭头的2 2s.)

最长的平衡子阵列是在元素+1的第一次出现和元素的最后出现之间.(第一个箭头+1和最后一个箭头:00111100001110)

备注:

最长的子阵列将始终位于D的2个元素之间,其在[0,Dn]之间,其中Dn是D的最后一个元素.(前一示例中的Dn = 2)Dn是列表中1和0之间的总不平衡.(如果Dn为负,则为[Dn,0])

在这个例子中,这意味着我不需要"看"3s或4s

证明:

设Dn> 0.

如果存在由P(P> Dn)分隔的子阵列.由于0 <Dn <P,在到达等于P的D的第一个元素之前,我们到达一个等于Dn的元素.因此,由于列表的最后一个元素等于Dn,因此由Dns分隔的最长子阵列比由Ps分隔的子阵列最长.因此我们不需要查看Ps

出于同样的原因,P不能小于0

Dn <0的证明是相同的

现在让我们研究D,D不是随机的,2连续元素之间的差异总是1或-1.Ans在D和初始列表之间有一个简单的双射.因此,我有2个解决此问题的方法:

• 第一个是跟踪D中每个元素的第一个和最后一个出现在0和Dn之间(cf备注).
• 第二是将列表转换为D,然后在D上工作.

第一个解决方案

暂时我找不到比第一个更好的方法:

首先计算Dn(在O(n)中).DN = 2

第二个而不是创建D,创建一个字典,其中键是D的值(在[0和Dn]之间),每个键的值是一对(a,b),其中a是键的第一次出现和b最后.

Element   D DICTIONNARY
null      0 {0:(0,0)}
1         1 {0:(0,0) 1:(1,1)}
1         2 {0:(0,0) 1:(1,1) 2:(2,2)}
0         1 {0:(0,0) 1:(1,3) 2:(2,2)}
0         0 {0:(0,4) 1:(1,3) 2:(2,2)}
1         1 {0:(0,4) 1:(1,5) 2:(2,2)}
1         2 {0:(0,4) 1:(1,5) 2:(2,6)}
1         3 { 0:(0,4) 1:(1,5) 2:(2,6)}
1         4 {0:(0,4) 1:(1,5) 2:(2,6)}  
0         3{0:(0,4) 1:(1,5) 2:(2,6) }
0         2 {0:(0,4) 1:(1,5) 2:(2,9) }
0         1 {0:(0,4) 1:(1,10) 2:(2,9) } 
0         0 {0:(0,11) 1:(1,10) 2:(2,9) } 
1         1 {0:(0,11) 1:(1,12) 2:(2,9) } 
1         2 {0:(0,11) 1:(1,12) 2:(2,13)}
1         3 {0:(0,11) 1:(1,12) 2:(2,13)} 
0         2 {0:(0,11) 1:(1,12) 2:(2,15)} 

并且您选择了具有最大差异的元素:2:(2,15)并且是l [3:15] = 00111100001110(其中l = 1100111100001110).

时间复杂度:

2次传球,第一次传球给Dn,第二次传球给Dictionnary.找到词典中的最大值.

总数是O(n)

空间复杂度:

D:O中的当前元素(1)字典O(Dn)

因为这句话我不会在词典中带3和4

复杂度是O(n)时间和O(Dn)空间(平均情况Dn << n).

我想这种方法可能比词典更好.

任何建议都是受欢迎的.

希望能帮助到你

第二个解决方案(只是一个想法而不是真正的解决方案)

第二种方法是将列表转换为D.(因为很容易从D返回到列表中就可以了).(O(n)时间和O(1)空间,因为我将列表转换到位,即使它可能不是"有效"O(1))

然后从D你需要找到2个相同的元素,这是更远的appart.

它看起来像在链表中查找最长的循环,理查德布伦特算法的修改可能会返回最长的循环,但我不知道如何去做,并且需要O(n)时间和O(1)空间.

找到最长的周期后,返回第一个列表并打印出来.

该算法将花费O(n)时间和O(1)空间复杂度.

Answer 2

对数组中的所有元素求和，则 diff = (array.length - sum) 将是 0 和 1 的数量之差。

1. 如果 diff 等于 array.length/2，则最大子数组 = array。
2. 如果 diff 小于 array.length/2 则 1 多于 0。
3. 如果 diff 大于 array.length/2 则 0 多于 1。

对于情况 2 和 3，初始化两个指针，start 和 end 分别指向数组的开头和结尾。如果有更多的 1，则根据 array[start] = 1 还是 array[end] = 1 将指针向内移动（start++ 或 end--），并相应地更新 sum。在每个步骤中检查 sum = (end - start) / 2 。如果此条件为真，则 start 和 end 代表最大子数组的边界。

这里我们最终对数组进行了两次传递，一次计算总和，一次将指针向内移动。我们使用常量空间，因为我们只需要存储总和和两个索引值。

如果有人想敲出一些伪代码，我们非常欢迎:)