Google – Partition Array of 0 and 1
给一个数组，只包含0和1，找出一个partition的位置，使得左边0的个数和右边1的个数加起来和最大。
[Solution]
Brute Force, DP
[Solution #1]
Brute Force, 每个位置算左右两边0和1的个数.
O(n^2) time
[Solution #2]
DP，两个数组记录每个位置左边0的个数和右边1的个数。
O(3n) time, O(2n) space
[Solution #3]
DP with space optimization.
space可以优化到O(1), 用两个变量存左边0的个数和右边1的个数。leftZero从0开始，rightOne从(number of ones in the whole array)开始。从左向右扫，碰到0就leftZero++，碰到1就rightOne–.
Read full article from Google – Partition Array of 0 and 1
给一个数组，只包含0和1，找出一个partition的位置，使得左边0的个数和右边1的个数加起来和最大。
[Solution]
Brute Force, DP
[Solution #1]
Brute Force, 每个位置算左右两边0和1的个数.
O(n^2) time
[Solution #2]
DP，两个数组记录每个位置左边0的个数和右边1的个数。
O(3n) time, O(2n) space
[Solution #3]
DP with space optimization.
space可以优化到O(1), 用两个变量存左边0的个数和右边1的个数。leftZero从0开始，rightOne从(number of ones in the whole array)开始。从左向右扫，碰到0就leftZero++，碰到1就rightOne–.
// DP without space optimizationclass Solution { public int partitionArray(int[] nums) { if (nums == null || nums.length == 0) { return -1; } int n = nums.length; int[] leftZeroes = new int[n]; int[] rightOnes = new int[n]; leftZeroes[0] = nums[0] == 0? 1 : 0; rightOnes[n - 1] = nums[n - 1] == 1? 1 : 0; for (int i = 1; i < n; i++) { if (nums[i] == 0) { leftZeroes[i] = leftZeroes[i - 1] + 1; } else { leftZeroes[i] = leftZeroes[i - 1]; } } for (int i = n - 2; i >= 0; i--) { if (nums[i] == 1) { rightOnes[i] = rightOnes[i + 1] + 1; } else { rightOnes[i] = rightOnes[i + 1]; } } int result = 0; int maxSum = 0; for (int i = 0; i < n; i++) { if (leftZeroes[i] + rightOnes[i] > maxSum) { maxSum = leftZeroes[i] + rightOnes[i]; result = i; } } return result; }}// O(1) spaceclass Solution2 { public int partitionArray(int[] nums) { if (nums == null || nums.length == 0) { return -1; } int n = nums.length; int leftZero = 0; int rightOne = 0; for (int i = n - 1; i >= 0; i--) { if (nums[i] == 1) { rightOne++; } } int result = -1; int maxSum = 0; for (int i= 0; i < n; i++) { if (leftZero + rightOne > maxSum) { maxSum = leftZero + rightOne; result = i; } if (nums[i] == 0) { leftZero++; } else { rightOne--; } } return result; }} |
