所以,我有一个只包含0和1的数组.我必须找出包含相同数字0和1的最大子阵列.一个天真的方法可能是复杂的,O(n^2)因为我采用外循环中的每个元素,并在内循环中计算可能的子数组,并保持更新最大大小(如果找到).还有其他更好的方法(比如O(n))我可以使用吗？谢谢!
Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)
tem*_*def 23
这是一个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)时间内填充和搜索所有内容.
希望这可以帮助!