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

目录
  • 题目要求
  • 思路一：两次遍历
    • Java
    • C++
    • Rust
  • 思路二：一次遍历
    • Java
    • C++
    • Rust

题目要求

题目链接

思路一：两次遍历

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

  • 首先从后向前遍历，找[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++题解分割数组的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C++ LeetCode1780判断数字是否可以表示成三的幂的和

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C++ LeetCode1812判断国际象棋棋盘格子颜色

    目录 1812.判断国际象棋棋盘中一个格子的颜色 方法一:取模 AC代码 C++ 方法二:基于方法一的小改进 AC代码 C++ 1812.判断国际象棋棋盘中一个格子的颜色 力扣题目链接:leetcode.cn/problems/de… 给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标.下图是国际象棋棋盘示意图. 如果所给格子的颜色是白色,请你返回 true,如果是黑色,请返回 false . 给定坐标一定代表国际象棋棋盘上一个存在的格子.坐标第一个字符是字

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

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode672灯泡开关示例

    Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++题解leetcode817链表组件示例

    Java C++题解leetcode817链表组件示例

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 Java class Solution { public int numComponents(ListNode head, int[] nums) { int res = 0; Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); // 转存nums while (head != null) { if (set.cont

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • java中两个byte数组实现合并的示例

    今天在于硬件进行交互的过程中,要到了了需要两个数组进行合并,然后对数组进行反转和加密操作,以下是两个byte数组合并的方法. /** * * @param data1 * @param data2 * @return data1 与 data2拼接的结果 */ public static byte[] addBytes(byte[] data1, byte[] data2) { byte[] data3 = new byte[data1.length + data2.length]; Syste

  • golang实现数组分割的示例代码

    需求:给定一个数组和一个正整数,要求把数组分割成多个正整数大小的数组,如果不够分,则最后一个数组分到剩余的所有元素. 示例1: 数组:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],正整数:2 期望结果: [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]] 示例2: 数组:[1, 2, 3, 4, 5, 6, 7, 8, 9],正整数:2 期望结果: [[1, 2], [3, 4], [5, 6], [7, 8], [9]] 下面是我的实现代码:

  • java数据结构算法稀疏数组示例详解

    java数据结构算法稀疏数组示例详解

    目录 一.什么是稀疏数组 二.场景用法 1.二维数组转稀疏数组思路 2.稀疏数组转二维数组思路 3.代码实现 一.什么是稀疏数组 当一个数组a中大部分元素为0,或者为同一个值,那么可以用稀疏数组b来保存数组a. 首先,稀疏数组是一个数组,然后以一种特定的方式来保存上述的数组a,具体处理方法: 记录数组a一共有几行几列 记录a中有多少个不同的值 最后记录不同值的元素所在行列,以及具体的值,放在一个小规模的数组里,以缩小程序的规模. 这个小规模的数组,就是稀疏数组. 举个栗子,左侧是一个二维数组,一

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

随机推荐