目录题目要求思路一:两次遍历Javac++Rust思路二:一次遍历JavaC++Rust题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的
题目链接
题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好;
找到分界点的索引后,只需+1即可得到长度。
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; // 用例保证不出现
}
}
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; // 用例保证不出现
}
};
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; // 用例保证不出现
}
}
从前向后遍历每个节点,依次假设每个节点为最终分界点;
若当前值nums[i]<leftMax则重新划定分界,将当前节点纳入左区间;
找到最终结果节点索引值,将其+1即得答案。
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;
}
}
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;
}
};
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
}
}
以上就是Java C++题解LeetCode915分割数组示例的详细内容,更多关于Java C++题解分割数组的资料请关注编程网其它相关文章!
--结束END--
本文标题: JavaC++题解leetcode915分割数组示例
本文链接: https://www.lsjlt.com/news/170635.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0