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

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

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

題目要求

題目鏈接

思路一：兩次遍歷

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

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

找到分界點(diǎn)的索引后，只需+1即可得到長(zhǎng)度。

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

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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)
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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)
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

思路二：一次遍歷

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

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

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

找到最終結(jié)果節(jié)點(diǎn)索引值，將其+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;
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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
    }
}