空间高效的算法找出最大的平衡子阵列？高效、阵列、算法、最大
给出0和1的阵列，发现最大的子阵列使得零和1的数量是相等的。 这需要在O（n）时间及O（1）空间。
完成我有一个算法中它做它的O（n）时间及O（n）的空间。它采用了preFIX总和阵列和利用这样的事实，如果0和1的数量是相同的，然后 sumOfSubarray = lengthOfSubarray / 2
＃包括＆LT;的iostream＆GT;
＃定义男性15例
使用名字空间std;
无效getSum（INT改编[]，INT prefixsum []，诠释大小）{
INT I;
prefixsum [0] =改编[0] = 0;
prefixsum [1] =改编[1];
对于（i = 2; I＆LT; =大小;我++）{
prefixsum [I] = prefixsum [I-1] +改编[I];
}
}
无效的发现（INT A []，INT和放大器;启动，INT和放大器端）{
同时（开始＆LT;结束）{
INT中期=（起始+端）/ 2;
如果（（年底启动+ 1）== 2 *（A [结束] - 一个[开始-1]））
打破;
如果（（年底启动+ 1）＆GT; 2 *（A [结束] - 一个[开始-1]））{
如果（A [开始] == 0＆功放;＆放大器;一个[结束] == 1）
启动++;其他
结束 - ;
} 其他 {
如果（A [开始] == 1安培;＆放大器;一个[结束] == 0）
启动++;其他
结束 - ;
}
}
}
诠释的main（）{
INT大小，编曲[M]，PS [M]，开始= 1结束，宽度;
;
CIN＆GT;＆GT;大小;
改编[0] = 0;
结束=大小;
的for（int i = 1; I＆LT; =大小;我++）
CIN＆GT;＆GT;常用3 [I]
getSum（ARR，PS，大小）;
发现（PS，开始，结束）;
如果（开始！=结束）
的cout＆其中;≤（启动1） - ;＆所述;＆其中;≤（最终1） - ;＆所述; ENDL;否则COUT＆LT;＆LT;不SOLN \ N的;
返回0;
}
解决方案
现在，我的算法是O（n）时间及O（DN）的空间，DN是列表的总失衡的。
该解决方案不修改该列表。
令D为1和0在列表中找到的差异。
首先，让我们一步linearily通过列表和计算研发，只是为了看看它是如何工作的：
我要使用这个列表作为一个例子：L = 1100111100001110
元件D
空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'; -
寻找最长平衡子阵列相当于发现是越远APPART在D 2相等的元素。 （在这个例子中，2 2秒用箭头标记）。
最长的平衡子阵列单元+1的第一次出现和元素的最后一次出现的。 （第一箭+1和最后一个箭头：00111100001110）
注：
最长子阵列将永远是D的子元素是的 间[0，DN]其中Dn是用于在D。（DN = 2的最后一个元素 previous例子）DN是1和0之间的总失衡 名单。 （或[DN，0]如果DN为负）
在这个例子就意味着我不需要看3S或4S
证明：
让DN> 0
如果有一个子阵列由P（P> DN）分隔。自0℃ DN＆LT;磷， 到达D的第一个元素之前，它等于与P我们达到一 元等于DN。因此，由于该列表的最后一个元素等于到Dn，有一个最长子阵列按DNS比一个接Ps.And分隔符分隔因此我们并不需要看诗
P能够不低于0出于同样的原因
证明是相同的DN℃的
现在，让我们工作D，D不是随机的，连续的2元之差始终为1或-1。答案有D和初始列表之间的一个简单的双射。因此，我有2个方案来解决这个问题：
第一个是跟踪的每个的第一和最后的外观 元素在D中是介于0和DN（参见备注）。 第二个是把列表分为研发，然后制定D上。第一个解决方案
暂时我不能找到比一个更好的方法第一种：
首先计算DN（在为O（n））。 DN = 2
二，而不是建立研发，创建一个dictionnary，其中键是D的值（在[0和DN]），每个键的值是一对夫妇（A，B），其中一个是在第一次出现键和B是最后一个。
元件D DICTIONNARY
空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遍，第一个到caclulate DN，第二个建 dictionnary。 找到最大的dictionnary。
合计为O（n）
空间复杂度：
当前元素在D：O（1）dictionnary O（DN）
我不，因为这句话的取3和4的dictionnary
的复杂度为O（n）时间及O（DN）的空间（以平均情况下DN＆LT;＆LT; N）。
我想有可能是一个比一个dictionnary这种方法更好的方法。
任何建议是值得欢迎的。
希望它可以帮助
第二个解决方案（只是一个想法不是真正的解决方案）
继续将改变你的列表分为四（因为它很容易去从D-回到列表它的确定）的第二种方式。 （O（n）时间及O（1）空间，因为我改造名单的地方，尽管它可能不是一个有效O（1））
再从D您需要找到那些越远APPART 2相同的元素。
它看起来像寻找最长循环链表，理查德·布伦特算法可能会返回周期最长，但我不知道该怎么做，这将需要O（n）时间及O（1）空间。
一旦你找到了周期最长，回到第一个列表，并打印出来。
该算法将需要O（n）时间及O（1）空间复杂度。
given an array of 0s and 1s, find maximum subarray such that number of zeros and 1s are equal. This needs to be done in O(n) time and O(1) space.
I have an algo which does it in O(n) time and O(n) space. It uses a prefix sum array and exploits the fact that if the number of 0s and 1s are same then 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;
}
解决方案
Now my algorithm is O(n) time and O(Dn) space where Dn is the total imblance in the list.
This solution doesn't modify the list.
let D be the difference of 1s and 0s found in the list.
First, let's step linearily through the list and calculate D, just to see how it works:
I'm gonna use this list as an example : 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 <-
Finding the longest balanced subarray is equivalent to finding 2 equal elements in D that are the more far appart. (in this example the 2 2s marked with arrows.)
The longest balanced subarray is between first occurence of element +1 and last occurence of element. (first arrow +1 and last arrow : 00111100001110)
Remark:
The longest subarray will always be between 2 elements of D that are between [0,Dn] where Dn is the last element of D. (Dn = 2 in the previous example) Dn is the total imbalance between 1s and 0s in the list. (or [Dn,0] if Dn is negative)
In this example it means that I don't need to "look" at 3s or 4s
Proof:
Let Dn > 0 .
If there is a subarray delimited by P (P > Dn). Since 0 < Dn < P, before reaching the first element of D which is equal to P we reach one element equal to Dn. Thus, since the last element of the list is equal to Dn, there is a longest subarray delimited by Dns than the one delimited by Ps.And therefore we don't need to look at Ps
P cannot be less than 0 for the same reasons
the proof is the same for Dn <0
Now let's work on D, D isn't random, the difference between 2 consecutive element is always 1 or -1. Ans there is an easy bijection between D and the initial list. Therefore I have 2 solutions for this problem:
the first one is to keep track of first and last appearance of each element in D that are between 0 and Dn (cf remark). second is to transform the list into D, and then work on D.FIRST SOLUTION
For the time being I cannot find a better approach than the first one:
First calculate Dn (in O(n)) . Dn=2
Second instead of creating D, create a dictionnary where the keys are the value of D (between [0 and Dn]) and the value of each keys is a couple (a,b) where a is the first occurence of the key and b the last.
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)}
and you chose the element with the largest difference : 2:(2,15) and is l[3:15]=00111100001110 (with l=1100111100001110).
Time complexity :
2 passes, the first one to caclulate Dn, the second one to build the dictionnary. find the max in the dictionnary.
Total is O(n)
Space complexity:
the current element in D : O(1) the dictionnary O(Dn)
I don't take 3 and 4 in the dictionnary because of the remark
The complexity is O(n) time and O(Dn) space (in average case Dn << n).
I guess there is may be a better way than a dictionnary for this approach.
Any suggestion is welcome.
Hope it helps
SECOND SOLUTION (JUST AN IDEA NOT THE REAL SOLUTION)
The second way to proceed would be to transform your list into D. (since it's easy to go back from D to the list it's ok). (O(n) time and O(1) space, since I transform the list in place, even though it might not be a "valid" O(1) )
Then from D you need to find the 2 equal element that are the more far appart.
it looks like finding the longest cycle in a linked list, A modification of Richard Brent algorithm might return the longest cycle but I don't know how to do it, and it would take O(n) time and O(1) space.
Once you find the longest cycle, go back to the first list and print it.
This algorithm would take O(n) time and O(1) space complexity.
