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

推荐阅读:
食疗养生:女性常吃哪些食物能保健养颜  食药总局要求加强白酒质量安全监管  食品认证乱象:有钱就给有机食品证书  食品安全法中应该设立有奖举报制度  哪些健脑食品有助于增强孩子的记忆力  食药监总局:明确乳粉企业监督检查规定  什么叫转基因食品 如何判断转基因食品  教你辨别常见的几种带有转基因的食品  冬季食疗进补过度容易导致咽喉干痛  大雪节气吃什么食物可以缓解皮肤干燥 
评论列表
添加评论