find最大平衡子阵的空间高效algorithm?

给定一个0和1的数组,find最大的子数组,使得零和1的数量相等。 这需要在O(n)时间和O(1)空间中完成。

我有一个algorithm,它在O(n)时间和O(n)空间。 它使用前缀sum数组并利用这样的事实,即如果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; } 

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

此解决scheme不会修改列表。

设D是列表中find的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 <- 

find最长的平衡子阵,相当于在D中find2个相等的元素,它们是更远的元素。 (在这个例子中,标有箭头的2个2)。

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

备注:

最长的子arrays总是在D的2个元素之间,在[0,Dn]之间,其中Dn是D的最后一个元素(Dn = 2,在前面的例子中)Dn是列表中1和0之间的总不平衡。 (如果Dn为负,则为[Dn,0])

在这个例子中,这意味着我不需要“看”3秒或4秒

certificate:

让Dn> 0。

如果有一个由P(P> Dn)分隔的子数组。 由于0 <Dn <P,在到达等于P的D的第一个元素之前,我们到达一个等于Dn的元素。 因此,由于列表的最后一个元素等于Dn,所以有一个最长的由Dns分隔的子数组,而不是由P分隔的子数组。因此,我们不需要看Ps

由于相同的原因,P不能小于0

Dn <0的certificate是相同的

现在让我们研究D,D不是随机的,2个连续元素之间的差值始终为1或-1。 答:D和初始列表之间有一个简单的双射。 所以我有这个问题的两个解决scheme:

  • 第一个是跟踪D和Dn中每个元素的第一个和最后一个外观(参见注释)。
  • 二是将列表转换为D,然后在D上工作。

第一个解决scheme

目前我找不到比第一个更好的方法:

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

其次,不是创buildD,而是创build一个键是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)} 

你select了差别最大的元素:2(2,15),并且是l [3:15] = 00111100001110(其中l = 1100111100001110)。

时间复杂度:

第一个是Dn,第二个是构buildDictionnary。 在词典中find最大值。

总数是O(n)

空间复杂性:

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

因为这个评论,我没有在这个词典中拿3和4

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

我想这个方法可能比一个词典更好。

任何build议是值得欢迎的。

希望能帮助到你


第二个解决scheme(只是一个理念而不是真正的解决scheme)

第二种方法是把你的列表变成D(因为从D返回列表很容易)。 (O(n)时间和O(1)空间,因为我将这个列表转换到位,尽pipe它可能不是一个“有效”的O(1))

然后从D你需要find2个相等的元素是更远的appart。

它看起来像在一个链表中find最长的循环。Richard Brentalgorithm的修改可能会返回最长的循环,但是我不知道如何去做,它需要O(n)个时间和O(1)空间。

一旦find最长的循环,回到第一个列表并打印出来。

这个algorithm将花费O(n)时间和O(1)空间复杂度。

不同的做法,但仍然O(n)时间和记忆。 从尼尔的build议开始,把0当作-1。

符号: A[0, …, N-1] – 大小为N的数组, f(0)=0, f(x)=A[x-1]+f(x-1)

如果你画f ,你会看到,你所寻找的是f(m)=f(n), m=n-2k ,其中k-正自然。 更准确地说,只有x使得A[x]!=A[x+1] (以及数组中的最后一个元素),您必须检查f(x)是否已经出现。 不幸的是,现在我看不出有数组B[-N+1…N-1]在哪里存储这样的信息。

为了完成我的想法: B[x]=-1最初, B[x]=pp = min k: f(k)=x 。 algorithm是(仔细检查,因为我很累):

 fx = 0 B = new array[-N+1, …, N-1] maxlen = 0 B[0]=0 for i=1…N-1 : fx = fx + A[i-1] if B[fx]==-1 : B[fx]=i else if ((i==N-1) or (A[i-1]!=A[i])) and (maxlen < iB[fx]): We found that A[B[fx], …, i] is best than what we found so far maxlen = iB[fx] 

编辑 :两个床上的想法(=躺在床上的时候:P):

1)你可以按照子arrays的长度对结果进行二进制search,这会给O(n log n)时间和O(1)存储器algorithm。 我们使用函数g(x)=x - x mod 2 (因为总和为0的子数组总是偶数长度)。 如果整个数组总和为0,则开始检查。如果是,则完成,否则继续。 我们现在假设0作为起点(我们知道有这样的长度和“求和到零性质”的子arrays)和g(N-1)作为终点(我们知道没有这样的子arrays)。 让我们做

  a = 0 b = g(N-1) while a<b : c = g((a+b)/2) check if there is such subarray in O(n) time if yes: a = c if no: b = c return the result: a (length of maximum subarray) 

检查具有给定长度L的“求和到零性质”的子阵是很简单的:

  a = 0 b = L fa = fb = 0 for i=0…L-1: fb = fb + A[i] while (fa != fb) and (b<N) : fa = fa + A[a] fb = fb + A[b] a = a + 1 b = b + 1 if b==N: not found found, starts at a and stops at b 

2) …你可以修改input数组吗? 如果是的话,如果O(1)的内存意味着,你没有使用额外的空间(恒定数量的元素除外) ,那么只需将您的前缀表值存储在您的input数组。 没有更多的空间使用(除了一些variables):D

再一次,仔细检查我的algorithm,因为我很厌倦,可以做错误的一个错误。

像尼尔一样,我认为考虑字母{±1}而不是{0,1}是很有用的。 假设不失一般性,至less有+1个-1。 下面的algorithm使用O(sqrt(n log n))位并在时间O(n)上运行,这是由于“AF”

注意:这个解决scheme不会假设input是可修改的和/或有浪费的位。 在编辑时,这个解决scheme是唯一一个既是O(n)时间也是o(n)空间的解决scheme。

使用O(n)位的更简单的版本,将前缀总和数组进行stream式处理,并标记每个值的首次出现。 然后它向后扫描,考虑0和sum(arr)之间的每个高度,在该高度的最大子arrays。 有些想法表明,最佳的是这些(记住这个假设)。 在Python中:

 sum = 0 min_so_far = 0 max_so_far = 0 is_first = [True] * (1 + len(arr)) for i, x in enumerate(arr): sum += x if sum < min_so_far: min_so_far = sum elif sum > max_so_far: max_so_far = sum else: is_first[1 + i] = False sum_i = 0 i = 0 while sum_i != sum: sum_i += arr[i] i += 1 sum_j = sum j = len(arr) longest = j - i for h in xrange(sum - 1, -1, -1): while sum_i != h or not is_first[i]: i -= 1 sum_i -= arr[i] while sum_j != h: j -= 1 sum_j -= arr[j] longest = max(longest, j - i) 

让空间减less的窍门来自于注意到我们依次扫描is_first ,尽pipe与其构造相反。 由于循环variables符合O(log n)位,我们将在每个O(√(n log n))步之后计算循环variables的检查点,而不是is_first 。 这是O(n /√(n log n))= O(√(n / log n))个检查点,总共O(√(n log n))位。 通过从检查点重新启动循环,我们按照is_first每个O(√(n log n))位部分is_first

(PS:问题陈述要求O(1)空间可能会也可能不是我的错 ,我真诚的道歉,如果是我拉了一个费马,并build议我解决问题比我想象的要困难得多了。)

如果你的algorithm确实在所有情况下都是有效的(请参阅我对你的问题的评论,注意对它的一些修正),注意前缀数组是唯一阻碍你持续记忆的目标。

检查find函数可以看出,这个数组可以被两个整数replace,从而消除了对input长度的依赖并解决了你的问题。 考虑以下:

  • 您只能依赖find函数中前缀数组中的两个值。 这是a[start - 1]a[end] 。 是的, startend变化,但这是否值得arrays?
  • 看看你的循环的进展。 最后, start递增或end递减1
  • 考虑到前面的陈述,如果你想用一个整数来replacea[start - 1]的值,你将如何更新它的值? 换句话说,对于循环中改变start值的每个转换,你可以怎么做来相应地更新整数以反映a[start - 1]的新值?
  • 这个过程可以用a[end]重复吗?
  • 实际上,如果a[start - 1]a[end]值可以用两个整数来反映,那么整个前缀数组是否不再有用呢? 不能因此被删除?

由于不需要前缀数组和所有存储依赖关系的input长度,所以algorithm将使用恒定的内存数量来实现其目标,从而使其成为O(n)时间和O(1)空间。

我宁愿你根据上面的见解自己解决这个问题,因为这是作业。 不过,我已经在下面提供了一个解决scheme供参考:

 #include <iostream> using namespace std; void find( int *data, int &start, int &end ) { // reflects the prefix sum until start - 1 int sumStart = 0; // reflects the prefix sum until end int sumEnd = 0; for( int i = start; i <= end; i++ ) sumEnd += data[i]; while( start < end ) { int length = end - start + 1; int sum = 2 * ( sumEnd - sumStart ); if( sum == length ) break; else if( sum < length ) { // sum needs to increase; get rid of the lower endpoint if( data[ start ] == 0 && data[ end ] == 1 ) { // sumStart must be updated to reflect the new prefix sum sumStart += data[ start ]; start++; } else { // sumEnd must be updated to reflect the new prefix sum sumEnd -= data[ end ]; end--; } } else { // sum needs to decrease; get rid of the higher endpoint if( data[ start ] == 1 && data[ end ] == 0 ) { // sumStart must be updated to reflect the new prefix sum sumStart += data[ start ]; start++; } else { // sumEnd must be updated to reflect the new prefix sum sumEnd -= data[ end ]; end--; } } } } int main() { int length; cin >> length; // get the data int data[length]; for( int i = 0; i < length; i++ ) cin >> data[i]; // solve and print the solution int start = 0, end = length - 1; find( data, start, end ); if( start == end ) puts( "No soln" ); else printf( "%d %d\n", start, end ); return 0; } 

这个algorithm是O(n)时间和O(1)空间。 它可能会修改源数组,但会将所有信息恢复回来。 所以它不适用于const数组。 如果这个难题有几个解决scheme,这个algorithmselect最接近arrays开始的解决scheme。 或者可能会修改提供所有解决scheme。

algorithm

variables:

  • p1 – 子arrays开始
  • p2 – 子arrays结束
  • d – 子arrays中1s和0s的差异

    1. 计算d ,如果d==0 ,停止。 如果d<0 ,则反转arrays,并在find平衡的子arrays后将其倒置。
    2. d > 0提前p2 :如果数组元素为1,则只减lessp2d 。 否则, p2应该通过forms为11*0子arrays,其中*是一些平衡的子arrays。 为了使回溯成为可能, 11*0? 变成0?*00 (其中?是子arrays旁边的值)。 然后d递减。
    3. 存储p1p2
    4. 回溯p2 :如果数组元素是1,只需递增p2 。 否则,我们find元素,在步骤2中更改。还原更改并传递格式为11*0子数组。
    5. 前进p1 :如果数组元素为1,则只增加p1 。 否则, p1应该通过forms为0*11子数组。
    6. 如果p2 - p1改善,则存储p1p2
    7. 如果p2在数组的末尾,则停止。 否则继续执行第4步。

在这里输入图像说明

它是如何工作的

algorithm遍历input数组中平衡子arrays的所有可能位置。 对于每个子arrays,位置p1p2尽可能地保持彼此距离最远,提供当地最长的子arrays。 在所有这些子arrays之间select具有最大长度的子arrays。

为了确定p1的下一个最佳位置,将其前进到1和0之间的平衡改变1的第一个位置。 (步骤5)。

为了确定p2的下一个最佳位置,将其推进到1s和0s之间的平衡被改变1的最后位置。 为了使之成为可能,第2步检测所有这样的位置(从数组末端开始),并以这种方式修改数组,以便可以用线性search来遍历这些位置。 (步骤4)。

执行步骤2时,可能会遇到两种可能的情况。 简单的一个:当发现值“1”时; 指针p2只是前进到下一个值,不需要特殊的处理。 但是,如果find值“0”,那么平衡就会走向错误的方向,有必要通过几个位,直到find正确的平衡。 所有这些位对algorithm都不感兴趣,停止p2会给出一个平衡的子arrays,这个arrays太短,或者是一个不平衡的子arrays。 结果, p2应该通过forms为11*0子arrays(从右到左, *表示任何平衡的子arrays)。 没有机会在其他方向走相同的路。 但是可以临时使用11*0模式中的一些位来允许回溯。 如果我们先将'1'改为'0',再把'1'改为最右边的'0'旁边的值,并清除最右边的'0'旁边的值: 11*0? -> 0?*00 11*0? -> 0?*00 ,那么我们有可能(首先)注意到这个模式,因为它从'0'开始,(第二个)为p2find下一个好的位置。

C ++代码:

 #include <cstddef> #include <bitset> static const size_t N = 270; void findLargestBalanced(std::bitset<N>& a, size_t& p1s, size_t& p2s) { // Step 1 size_t p1 = 0; size_t p2 = N; int d = 2 * a.count() - N; bool flip = false; if (d == 0) { p1s = 0; p2s = N; return; } if (d < 0) { flip = true; d = -d; a.flip(); } // Step 2 bool next = true; while (d > 0) { if (p2 < N) { next = a[p2]; } --d; --p2; if (a[p2] == false) { if (p2+1 < N) { a[p2+1] = false; } int dd = 2; while (dd > 0) { dd += (a[--p2]? -1: 1); } a[p2+1] = next; a[p2] = false; } } // Step 3 p2s = p2; p1s = p1; do { // Step 4 if (a[p2] == false) { a[p2++] = true; bool nextToRestore = a[p2]; a[p2++] = true; int dd = 2; while (dd > 0 && p2 < N) { dd += (a[p2++]? 1: -1); } if (dd == 0) { a[--p2] = nextToRestore; } } else { ++p2; } // Step 5 if (a[p1++] == false) { int dd = 2; while (dd > 0) { dd += (a[p1++]? -1: 1); } } // Step 6 if (p2 - p1 > p2s - p1s) { p2s = p2; p1s = p1; } } while (p2 < N); if (flip) { a.flip(); } } 

求和数组中的所有元素,然后diff =(array.length – sum)将是0和1的数目的差异。

  1. 如果diff等于array.length / 2,那么最大的子数组= array。
  2. 如果diff小于array.length / 2,那么比0更多的是1。
  3. 如果diff大于array.length / 2,那么有更多的0比1s。

对于情况2和3,初始化两个指针,开始和结束指向数组的开始和结束。 如果我们有更多的1,那么根据数组​​[开始] = 1或数组[结束] = 1向内移动指针(开始++或结束 – ),并相应地更新和。 在每一步检查sum =(结束 – 开始)/ 2。如果这个条件是真的,那么开始和结束代表最大的子arrays的边界。

在这里,我们最终做了两次数组,一次计算总和,一次向内移动指针。 而我们正在使用恒定的空间,因为我们只需要存储总和和两个索引值。

如果有人想打倒一些伪代码,你不仅欢迎:)

这是一个动作解决scheme,看起来像是缩放O(n)。 虽然它可能更像O(n log n)。 它绝对只使用O(1)内存。

警告我没有检查它是多么完整。 我可能会错过一些情况。

 protected function findLongest(array:Array, start:int = 0, end:int = -1):int { if (end < start) { end = array.length-1; } var startDiff:int = 0; var endDiff:int = 0; var diff:int = 0; var length:int = end-start; for (var i:int = 0; i <= length; i++) { if (array[i+start] == '1') { startDiff++; } else { startDiff--; } if (array[end-i] == '1') { endDiff++; } else { endDiff--; } //We can stop when there's no chance of equalizing anymore. if (Math.abs(startDiff) > length - i) { diff = endDiff; start = end - i; break; } else if (Math.abs(endDiff) > length - i) { diff = startDiff; end = i+start; break; } } var bit:String = diff > 0 ? '1': '0'; var diffAdjustment:int = diff > 0 ? -1: 1; //Strip off the bad vars off the ends. while (diff != 0 && array[start] == bit) { start++; diff += diffAdjustment; } while(diff != 0 && array[end] == bit) { end--; diff += diffAdjustment; } //If we have equalized end. Otherwise recurse within the sub-array. if (diff == 0) return end-start+1; else return findLongest(array, start, end); } 

我认为这是不可能的,以下面的方式存在一个O(1)的algorithm。 假设你在每一个位上迭代一次。 这需要一个需要O(log n)空间的计数器。 可能有人会认为n本身就是问题实例的一部分,那么对于长度为k:k + 2-log k的二进制string,您有一个input长度。 不pipe你如何查看它们,你需要一个额外的variables,以防你需要一个索引进入该数组,这已经使得它不是O(1)。

通常你没有这个问题,因为你有一个大小为n的问题,inputn个大小为log k的数字,它加起来就是nlog k。 这里一个长度为log k的variables就是O(1)。 但是在这里我们的log k只是1.所以我们只能引入一个长度不变的帮助variables(我的意思是非常稳定,无论n是多大都必须限制)。

这里的一个问题就是问题的描述是否可见。 在计算机理论中,你必须非常小心你的编码。 例如,如果切换到一元编码,则可以使NP问题为多项式(因为那么input大小比在n元(n> 1)编码中指数大。

至于n的input只有2-log n的大小,一定要小心。 当你在这个O(n)的情况下说话 – 这实际上是一个algorithm,它是O(2 ^ n)(这是没有意义的,我们需要讨论 – 因为可以争论n本身是否是描述的一部分,不)。

我有这个algorithm运行在O(n)时间和O(1)空间。

它利用简单的“缩小然后扩大”的伎俩。 代码中的注释。

 public static void longestSubArrayWithSameZerosAndOnes() { // You are given an array of 1's and 0's only. // Find the longest subarray which contains equal number of 1's and 0's int[] A = new int[] {1, 0, 1, 1, 1, 0, 0,0,1}; int num0 = 0, num1 = 0; // First, calculate how many 0s and 1s in the array for(int i = 0; i < A.length; i++) { if(A[i] == 0) { num0++; } else { num1++; } } if(num0 == 0 || num1 == 0) { System.out.println("The length of the sub-array is 0"); return; } // Second, check the array to find a continuous "block" that has // the same number of 0s and 1s, starting from the HEAD and the // TAIL of the array, and moving the 2 "pointer" (HEAD and TAIL) // towards the CENTER of the array int start = 0, end = A.length - 1; while(num0 != num1 && start < end) { if(num1 > num0) { if(A[start] == 1) { num1--; start++; } else if(A[end] == 1) { num1--; end--; } else { num0--; start++; num0--; end--; } } else if(num1 < num0) { if(A[start] == 0) { num0--; start++; } else if(A[end] == 0) { num0--; end--; } else { num1--; start++; num1--; end--; } } } if(num0 == 0 || num1 == 0) { start = end; end++; } // Third, expand the continuous "block" just found at step #2 by // moving "HEAD" to head of the array and "TAIL" to the end of // the array, while still keeping the "block" balanced(containing // the same number of 0s and 1s while(0 < start && end < A.length - 1) { if(A[start - 1] == 0 && A[end + 1] == 0 || A[start - 1] == 1 && A[end + 1] == 1) { break; } start--; end++; } System.out.println("The length of the sub-array is " + (end - start + 1) + ", starting from #" + start + " to #" + end); 

}

线性时间,恒定的空间。 让我知道是否有任何错过我错过了。
在python3中testing。

 def longestBalancedSubarray(A): lo,hi = 0,len(A)-1 ones = sum(A);zeros = len(A) - ones while lo < hi: if ones == zeros: break else: if ones > zeros: if A[lo] == 1: lo+=1; ones-=1 elif A[hi] == 1: hi+=1; ones-=1 else: lo+=1; zeros -=1 else: if A[lo] == 0: lo+=1; zeros-=1 elif A[hi] == 0: hi+=1; zeros-=1 else: lo+=1; ones -=1 return(A[lo:hi+1])