给定一个数组，它的元素是0和1，请找出最大的子数组，使这个子数组的元素中0和1的个数相等。

例如，输入：
{ 0, 0, 1, 0, 1, 0, 0 }
输出：
Largest subarray is { 0, 1, 0, 1 } or { 1, 0, 1, 0}

我们马上能想到的一种算法是遍历所有的子数组，对于每个子数组，我们计算它包含的所有0和1的个数。如果子数组中包含的0和1的个数相等，我们就判断此子数组的长度是否和之前记录的最长子数组相等，如果它更大，那么就记录它，直到遍历完所有的子数组。这种方案的时间复杂度是O(n³)，因为有n²个子数组，并且我们必须话费O(n)的时间去遍历每个子数组，以求出它包含的0和1的个数。当然，通过优化，我们可以在O(1)时间内计算出0和1的个数，这样这种方法可以优化到O(n²)的时间复杂度。

还有另一种方法，可以在线性时间内解决问题。这种方案是这样，把数组中的元素0替换成-1，并找出和等于0的最大子数组。为了找到和等于0的最大子数组，我们可以创建一个空的Map用以存储和等于给定值的所有子数组的结束下标。我们遍历整个数组，然后维护到目前为止便利到的所有元素。

c++语言实现：

#include
using namespace std;

// Function to find maximum length sub-array having equal number
// of 0’s and 1’s
void maxLenSubarray(int arr[], int n)
{
// create an empty map to store ending index of first sub-array
// having some sum
unordered_map map;

// insert (0, -1) pair into the set to handle the case when
// sub-array with sum 0 starts from index 0
map[0] = -1;

// len stores the maximum length of sub-array with sum 0
int len = 0;

// stores ending index of maximum length sub-array having sum 0
int ending_index = -1;

int sum = 0;

// Traverse through the given array
for (int i = 0; i < n; i++) { // sum of elements so far (replace 0 with -1) sum += (arr[i] == 0)? -1 : 1; // if sum is seen before if (map.find(sum) != map.end()) { // update length and ending index of maximum length // sub-array having sum 0 if (len < i - map[sum]) { len = i - map[sum]; ending_index = i; } } // if sum is seen for first time, insert sum with its // index into the map else map[sum] = i; } // print the sub-array if present if (ending_index != -1) cout << "[" << ending_index - len + 1 << ", " << ending_index << "]"; else cout << "No sub-array exists"; } // main function int main() { int arr[] = { 0, 0, 1, 0, 1, 0, 0 }; int n = sizeof(arr) / sizeof(arr[0]); maxLenSubarray(arr, n); return 0; } [/cpp] Java语言实现： [java] import java.util.Map; import java.util.HashMap; class MaxLengthSubArray { // Function to find maximum length sub-array having equal number // of 0's and 1's public static void maxLenSubarray(int arr[]) { // n is length of the array int n = arr.length; // create an empty Hash Map to store ending index of first // sub-array having some sum Map map = new HashMap();

// insert (0, -1) pair into the set to handle the case when
// sub-array with sum 0 starts from index 0
map.put(0, -1);

// len stores the maximum length of sub-array with sum 0
int len = 0;

// stores ending index of maximum length sub-array having sum 0
int ending_index = -1;

int sum = 0;

// Traverse through the given array
for (int i = 0; i < n; i++) { // sum of elements so far (replace 0 with -1) sum += (arr[i] == 0)? -1: 1; // if sum is seen before if (map.containsKey(sum)) { // update length and ending index of maximum length // sub-array having sum 0 if (len < i - map.get(sum)) { len = i - map.get(sum); ending_index = i; } } // if sum is seen for first time, insert sum with its // index into the map else map.put(sum, i); } // print the sub-array if present if (ending_index != -1) System.out.println("[" + (ending_index - len + 1) + ", " + ending_index + "]"); else System.out.println("No sub-array exists"); } // main function public static void main (String[] args) { int arr[] = { 0, 0, 1, 0, 1, 0, 0 }; maxLenSubarray(arr); } } [/java]
输出: [1,4]

以上两种方案的时间复杂度都是O(n)，空间复杂度都是o(n)。

| 2017年7 月28日 星期五 06:33:53| 算法设计| 添加评论|