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; } 

Answer 1

现在我的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）空间复杂度。

Answer 2

不同的做法，但仍然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]=p当p = 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，因为我很厌倦，可以做错误的一个错误。

Answer 3

像尼尔一样，我认为考虑字母{±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议我解决问题比我想象的要困难得多了。）

Answer 4

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

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

• 您只能依赖find函数中前缀数组中的两个值。 这是a[start - 1]和a[end] 。 是的， start和end变化，但这是否值得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; } 

Answer 5

这个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，则只减lessp2和d 。 否则， p2应该通过forms为11*0子arrays，其中*是一些平衡的子arrays。 为了使回溯成为可能， 11*0? 变成0?*00 （其中?是子arrays旁边的值）。 然后d递减。
  3. 存储p1和p2 。
  4. 回溯p2 ：如果数组元素是1，只需递增p2 。 否则，我们find元素，在步骤2中更改。还原更改并传递格式为11*0子数组。
  5. 前进p1 ：如果数组元素为1，则只增加p1 。 否则， p1应该通过forms为0*11子数组。
  6. 如果p2 - p1改善，则存储p1和p2 。
  7. 如果p2在数组的末尾，则停止。 否则继续执行第4步。

它是如何工作的

algorithm遍历input数组中平衡子arrays的所有可能位置。 对于每个子arrays，位置p1和p2尽可能地保持彼此距离最远，提供当地最长的子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(); } } 

Answer 6

求和数组中的所有元素，然后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的边界。

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

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

Answer 7

这是一个动作解决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); } 

Answer 8

我认为这是不可能的，以下面的方式存在一个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本身是否是描述的一部分，不）。

Answer 9

我有这个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); 

}

Answer 10

线性时间，恒定的空间。 让我知道是否有任何错过我错过了。
在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])