小编vas*_*sav的帖子

给定0和1的数组,找到最大子阵列,使得零和1的数量相等.这需要在O(n)时间和O(1)空间中完成.

我有一个算法在O(n)时间和O(n)空间中进行.它使用前缀和数组,并利用如果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() { …

给定两个二叉搜索树,按时间复杂度O(n)和空间复杂度按升序打印节点:O(1)

树木无法修改.只允许遍历.

我面临的问题是O(1)空间解决方案.如果没有这种限制,它可以很容易地解决.