Java C++題解leetcode915分割數(shù)組示例
更新時間：2022年11月02日 17:12:45 作者：AnjaVon
這篇文章主要為大家介紹了Java C++題解leetcode915分割數(shù)組示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
題目要求
思路一：兩次遍歷
題目的意思也就是左半邊數(shù)組的最大值小于等于右半邊數(shù)組的最小值，那么就找這個分界點就好；
- 首先從后向前遍歷，找[i,n−1]里最小的值；
- 然后從前向后遍歷，找[0,i]里最大的值；
- 然后找滿足max[i]<=min[i+1]的分割點i；
- 可以將2、3兩步結(jié)合為一步完成，由于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)
}
}
- 時間復(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)
}
};
- 時間復(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)
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
思路二：一次遍歷
從前向后遍歷每個節(jié)點，依次假設(shè)每個節(jié)點為最終分界點；
- 維護(hù)當(dāng)前遍歷節(jié)點的最大值maxx，即[0,i]內(nèi)；
- 記錄假設(shè)分界點i及其對應(yīng)左半邊數(shù)組最大值leftMax；
若當(dāng)前值nums[i]<leftMax則重新劃定分界，將當(dāng)前節(jié)點納入左區(qū)間；
找到最終結(jié)果節(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;
}
}
- 時間復(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;
}
};
- 時間復(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
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
以上就是Java C++題解leetcode915分割數(shù)組示例的詳細(xì)內(nèi)容，更多關(guān)于Java C++題解分割數(shù)組的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++實現(xiàn)LeetCode(92.倒置鏈表之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(倒置鏈表之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家介紹了MFC實現(xiàn)簡單的計算器，文中介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-08-08
udp socket客戶端和udp服務(wù)端程序示例分享
這篇文章主要介紹了udp socket客戶端和udp服務(wù)端程序示例,需要的朋友可以參考下2014-03-03
VSCode遠(yuǎn)程開發(fā)調(diào)試服務(wù)器c/c++代碼
語音相關(guān)的好多項目要在linux上跑，但代碼開發(fā)大多是在PC機上，本篇簡單介紹一下怎么在個人電腦上用VSCode遠(yuǎn)程開發(fā)調(diào)試服務(wù)器上的c/c++代碼。感興趣的朋友跟隨小編一起看看吧2020-04-04
C++簡單實現(xiàn)RPC網(wǎng)絡(luò)通訊的示例詳解
RPC是遠(yuǎn)程調(diào)用系統(tǒng)簡稱，它允許程序調(diào)用運行在另一臺計算機上的過程，就像調(diào)用本地的過程一樣。本文將用C++簡單實現(xiàn)RPC網(wǎng)絡(luò)通訊，感興趣的可以了解一下2023-04-04
requires?是?C++20?中引入的一個新關(guān)鍵字，用于在函數(shù)模板或類模板中聲明所需的一組語義要求，它可以用來限制模板參數(shù)，類似于?typename?和?class?關(guān)鍵字，這篇文章主要介紹了C++?requires關(guān)鍵字簡介,需要的朋友可以參考下2023-05-05
C語言實現(xiàn)學(xué)生信息管理系統(tǒng)(文件操作)
這篇文章主要介紹了C語言實現(xiàn)學(xué)生信息管理系統(tǒng)，增加了文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
C?語言內(nèi)存管理指對系統(tǒng)內(nèi)存的分配、創(chuàng)建、使用這一系列操作。在內(nèi)存管理中，由于是操作系統(tǒng)內(nèi)存，使用不當(dāng)會造成畢竟麻煩的結(jié)果。本文將從系統(tǒng)內(nèi)存的分配、創(chuàng)建出發(fā)，并且使用例子來舉例說明內(nèi)存管理不當(dāng)會出現(xiàn)的情況及解決辦法2022-05-05
這篇文章主要和大家分享幾個C++?結(jié)構(gòu)體的案例練習(xí)，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下，希望能夠給你帶來幫助2022-04-04
這篇文章主要介紹了C++設(shè)計模式之單例模式,本文同時給出了4種單例模式的實現(xiàn)代碼,需要的朋友可以參考下2014-09-09