資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將陣列劃分成不相交區間
假設我們有一個數組 A，我們需要將其劃分為兩個子陣列 left 和 right，使得：
left 子陣列中的每個元素都小於或等於 right 子陣列中的每個元素。
left 和 right 子陣列都不為空。
left 子陣列具有儘可能小的尺寸。
我們需要找到這種劃分後 left 的長度。保證存在這樣的劃分。
例如，如果輸入是 [5, 0, 3, 8, 6]，則輸出將是 3，因為 left 陣列將是 [5, 0, 3]，而 right 子陣列將是 [8, 6]。
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小，建立一個大小為 n 的陣列 maxx
minVal := A 的最後一個元素
maxx[0] := A[0]
對於 i 從 1 到 n – 1
maxx[i] := A[i] 和 A[i – 1] 中的最大值
ans := A 的大小 – 1
對於 i 從 n – 1 到 1
minVal := minVal 和 A[i] 中的最小值
如果 minVal >= max[i – 1]，則 ans := i
返回 ans
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int partitionDisjoint(vector <int>& A) {
int n = A.size();
vector <int> maxx(n);
int minVal = A[n - 1];
maxx[0] = A[0];
for(int i = 1; i < n; i++){
maxx[i] = max(A[i], maxx[i - 1]);
}
int ans = A.size() - 1;
for(int i = n - 1; i >= 1; i--){
minVal = min(minVal, A[i]);
if(minVal >= maxx[i - 1]){
ans = i;
}
}
return ans;
}
};
main(){
vector<int> v1 = {5,0,3,8,6};
Solution ob;
cout << (ob.partitionDisjoint(v1));
}輸入
[5,0,3,8,6]
輸出
3
更新於: 2020-04-30
358 次瀏覽
廣告