Java C++题解leetcode915分割数组示例_Java教程_编程语言

Java C++题解leetcode915分割数组示例

2023-02-08 学习力0

核心提示：目录题目要求思路一：两次遍历JavaC++Rust思路二：一次遍历JavaC++Rust题目要求题目链接思路一：两次遍历题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值，那么就找这个分界点就好；首先从后向前遍历，找[i,n−1]里最小的值；然后从前向后遍历

题目要求

题目链接

Java C++题解leetcode915分割数组示例

思路一：两次遍历

题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值，那么就找这个分界点就好；

首先从后向前遍历，找[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; // 用例保证不出现
    }
}

时间复杂度：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; // 用例保证不出现
    }
};

时间复杂度：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; // 用例保证不出现
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

思路二：一次遍历

从前向后遍历每个节点，依次假设每个节点为最终分界点；

维护当前遍历节点的最大值maxx，即[0,i]内；
记录假设分界点i及其对应左半边数组最大值leftMax；

若当前值nums[i]<leftMax则重新划定分界，将当前节点纳入左区间；

找到最终结果节点索引值，将其+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
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

以上就是Java C++题解leetcode915分割数组示例的详细内容，更多关于Java C++题解分割数组的资料请关注其它相关文章！

原文地址：https://juejin.cn/post/7157967114857349157

免责声明：本文仅代表作者个人观点，与乐学笔记（本网）无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
本网站有部分内容均转载自其它媒体，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责，若因作品内容、知识产权、版权和其他问题，请及时提供相关证明等材料并与我们留言联系，本网站将在规定时间内给予删除等相关处理.