发现最大子阵列与相等数量的0和1的 [英] Finding the largest subarray with equal number of 0's and 1's

问题描述

所以，我也只包含0和1的阵列。我必须找出含有相同数量的0和1的最大子阵列。一个人可以是天真的做法具有复杂性，因为为O（n ^ 2）在那里我参加外环的每一个元素，并计算出可能的子阵列在内部循环，并保持更新的最大尺寸如果发现。是否有其他更好的方法（类似于O（N）），我可以使用？谢谢！

 输入：常用3 [] = {1，0，1，1，1，0，0}
输出：1〜6（开始和结束的输出子数组的索引）
 

解决方案

下面是一个为O​​（n） - 时间，为O（n）空间的算法。我不知道这是最佳的，但它打败二次的时间。

的基本思想如下。假设用户从阵列到右侧的记录的左侧进行扫描，在每个步骤中，1的数目和0的数目之间的差。如果你写这些值出在每一步，你会得到这样的：

  1，0，1，0，0，0，0
0，1，0，1，0，-1，-2，-3
 

如果你有一个子阵列0和1的相同，那么0和1的子数组的开始的净差额将子阵列后等于净数量。因此，这个问题可以被重新定义为试图找到辅助阵列是平等的，相距甚远尽可能在两个相等的值。

好消息是，阵列​​中的每个条目是-N和+ N之间，这样就可以使一个2n + 1个元素表，并存储在它的第一次也是最后一次出现的每个数字的指标。从这里，可以很容易地找到最长的范围内。总体而言，这需要O（n）的空间，什么都可以填充，并搜查O（n）时间。

希望这有助于！

So, I have an array containing only 0's and 1's. I have to find out the largest subarray containing equal number of 0's and 1's. One can be a naive approach have complexity as O(n^2) where I take every element in outer loop and calculate possible subarrays in the inner loop and keep updating the maximum size, if found. Is there any other better approach (something like O(n)) that I can use? Thanks!

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

解决方案

Here's an O(n)-time, O(n)-space algorithm. I'm not sure it's optimal, but it beats quadratic time.

The basic idea is the following. Suppose that you scan from the left of the array to the right recording, at each step, the difference between the number of 1s and the number of 0s. If you write these values out at each step, you'll get something like this:

  1,   0,   1,    0,    0,   0,   0
0,   1,   0,   1,    0,    -1,  -2,  -3

If you have a sub array with the same number of 0s and 1s, then the net difference of 0s and 1s at the start of the subarray will equal the net number after the subarray. Therefore, this problem can be reframed as trying to find two equal values in the auxiliary array that are equal and as far apart as possible.

The good news is that every entry in the array is between -n and +n, so you can make a 2n+1 element table and store in it the indices of the first and last time each number appears. From there, it's easy to find the longest range. Overall, this needs O(n) space and everything can be populated and searched in O(n) time.

Hope this helps!

这篇关于发现最大子阵列与相等数量的0和1的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！