How to Partition Array into Disjoint Intervals?
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:143 次
Given an array A, partition it into two (contiguous) subarrays left and right so that:
- Every element in left is less than or equal to every element in right.
- left and right are non-empty.
- left has the smallest possible size.
Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.
Example 1:
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]Note:
2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.
Bruteforce Algorithm to Partition Array into Disjoint Intervals
Obviously, we can bruteforce the possible parition solutions, and check if every element in left is less than or equalt to the numbers in the right partition. But this is slow. It will need O(N^2) time.
Preprocess the Max Left and Right Array
We can pre-process the array twice to obtain a max left and max right array. Then, we need to check when the first time we have maxLeft is smaller or equal to the maxRight.
It turns out we only need to allocate an O(N) array to store e.g. maxRight, and updating a current MaxLeft when we iterating the array from left.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: int partitionDisjoint(vector<int>& A) { vector<int> minRight(A.size(), INT_MAX); minRight[A.size() - 1] = A.back(); for (int i = A.size() - 2; i >= 0; -- i) { minRight[i] = min(minRight[i + 1], A[i]); } int maxLeft = -1; for (int i = 0; i + 1 < A.size(); ++ i) { maxLeft = max(maxLeft, A[i]); if (maxLeft <= minRight[i + 1]) { return i + 1; } } return A.size(); // return something to make compiler happy } }; |
class Solution {
public:
int partitionDisjoint(vector<int>& A) {
vector<int> minRight(A.size(), INT_MAX);
minRight[A.size() - 1] = A.back();
for (int i = A.size() - 2; i >= 0; -- i) {
minRight[i] = min(minRight[i + 1], A[i]);
}
int maxLeft = -1;
for (int i = 0; i + 1 < A.size(); ++ i) {
maxLeft = max(maxLeft, A[i]);
if (maxLeft <= minRight[i + 1]) {
return i + 1;
}
}
return A.size(); // return something to make compiler happy
}
};O(N) time and O(N) space.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:abc是一个任意三位数 两条直角边的长度是两个质数 小羊小鹿和小熊共同修建一个小水池 wordpress 文章发布出现“定时发布失败”的原因及解决方法 wordpress 数据库表前缀修改方法 wordpress技巧:为标签链接添加rel=”nofollow”属性 wordpress 4.0 新增自定义图标插件安装 WordPress在线文件管理插件:FileBrowser 设置wordpress文章标题高亮的代码 免插件实现WordPress文章置顶的方法
- 评论列表
-
- 添加评论