How to Partition Array into Disjoint Intervals?

  • 时间:2020-09-18 17:26:09
  • 分类:网络文摘
  • 阅读:89 次

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) —

推荐阅读:
香蕉对身体健康有很多好处,教你用香蕉做一道美味粥吧  香菇与洋葱搭配在一起营养全面,使得保健功效会更好  分数的运算古代的分数除法  巧用份数解决问题  有趣的迷路问题  华罗庚的回归  不可微——不吃饭  “健忘”的维纳  闭门羹  比上帝还挑剔的人 
评论列表
添加评论