Java C++題解leetcode915分割數(shù)組示例

更新時間：2022年11月02日 17:12:45 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode915分割數(shù)組示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目要求

題目鏈接

思路一：兩次遍歷

題目的意思也就是左半邊數(shù)組的最大值小于等于右半邊數(shù)組的最小值，那么就找這個分界點就好；

首先從后向前遍歷，找[i,n−1]里最小的值；
然后從前向后遍歷，找[0,i]里最大的值；
然后找滿足max[i]<=min[i+1]的分割點i；
可以將2、3兩步結合為一步完成，由于iii從前向后不斷增大，所以用后面（較大）的值覆蓋更新之前的值。

找到分界點的索引后，只需+1即可得到長度。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] minn = new int[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = Math.min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保證不出現(xiàn)
    }
}

時間復雜度：O(n)
空間復雜度：O(n)

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        int minn[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保證不出現(xiàn)
    }
};

時間復雜度：O(n)
空間復雜度：O(n)

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut minn = vec![nums[n - 1]; n + 10];
        for i in (0..(n - 1)).rev() {
            minn[i] = minn[i + 1].min(nums[i]);
        }
        let mut maxx = 0;
        for i in 0..(n - 1) {
            maxx = maxx.max(nums[i]);
            if (maxx <= minn[i + 1]) {
                return (i + 1) as i32;
            }
        }
        return 1; // 用例保證不出現(xiàn)
    }
}

時間復雜度：O(n)
空間復雜度：O(n)

思路二：一次遍歷

從前向后遍歷每個節(jié)點，依次假設每個節(jié)點為最終分界點；

維護當前遍歷節(jié)點的最大值maxx，即[0,i]內(nèi)；
記錄假設分界點i及其對應左半邊數(shù)組最大值leftMax；

若當前值nums[i]<leftMax則重新劃定分界，將當前節(jié)點納入左區(qū)間；

找到最終結果節(jié)點索引值，將其+1即得答案。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
}

時間復雜度：O(n)
空間復雜度：O(1)

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.size() - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
};

時間復雜度：O(n)
空間復雜度：O(1)

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let (mut leftMax, mut res, mut maxx) = (nums[0], 0, nums[0]);
        for i in 1..(nums.len()-1) {
            maxx = maxx.max(nums[i]);
            if nums[i] < leftMax {
                leftMax = maxx;
                res = i as i32;
            }
        }
        res + 1
    }
}