資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中建立最大數
假設我們有兩個長度分別為m和n的陣列，其中包含代表兩個數字的0-9的數字。我們必須從這兩個數字的數字中建立一個長度為k的最大數字，該數字小於m+n。我們必須記住，來自同一個陣列的數字的相對順序必須保持不變。我們必須找到k位數字的陣列。因此，如果輸入類似於[3,4,7,5]和[9,1,3,5,8,4]，並且k=5，則答案將為[9,8,7,5,4]。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式mergeThem()，它將接收一個數組nums1和一個數組nums2，
- 定義一個數組ret
- i := 0, j := 0, n := nums1的長度, m := nums2的長度
- 當(i < n 或 j < m)時，執行：
- 如果呼叫函式greater(nums1, nums2, i, j)為真，則：
- 將nums1[i]插入到ret的末尾
- (i加1)
- 否則
- 將nums2[j]插入到ret的末尾
- (j加1)
- 如果呼叫函式greater(nums1, nums2, i, j)為真，則：
- 返回ret
- 定義一個函式modify()，它將接收一個數組v和k，
- 定義一個棧st
- 定義一個數組ret
- 對於初始化i := 0，當i < v的長度時，更新(i加1)，執行：
- x := v[i]
- 當(st不為空且st的頂部元素 < x 且 st的長度 + v的長度 – i – 1 >= k)時，執行：
- 從st中刪除元素
- 如果st的長度 < k，則：
- 將x插入到st中
- 當(st不為空)時，執行：
- 將st的頂部元素插入到ret的末尾
- 從st中刪除元素
- 反轉陣列ret
- 返回ret
- 定義一個函式greater()，它將接收一個數組a，一個數組b，i，j，
- 當(i < a的長度且j < b的長度且a[i]等於b[j])時，執行：
- i加1，j加1
- 當j == b的長度或i < a的長度且a[i] > b[j]時返回真
- 在主方法中執行以下操作
- 定義一個數組ret
- n := nums1的長度
- m := nums2的長度
- 對於初始化i := 0，當i <= k時，更新(i加1)，執行：
- 如果i <= n且(k - i) <= m，則：
- 定義一個數組candidate = mergeThem(modify(nums1, i), modify(nums2, k - i))
- 如果greater(candidate, ret, 0, 0)為真，則：
- ret := candidate
- 如果i <= n且(k - i) <= m，則：
- 返回ret
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> mergeThem(vector<int> nums1, vector<int> nums2)
{
vector<int> ret;
int i = 0;
int j = 0;
int n = nums1.size();
int m = nums2.size();
while (i < n || j < m) {
if (greater(nums1, nums2, i, j)) {
ret.push_back(nums1[i]);
i++;
}
else {
ret.push_back(nums2[j]);
j++;
}
}
return ret;
}
vector<int> modify(vector<int>& v, int k)
{
stack<int> st;
vector<int> ret;
for (int i = 0; i < v.size(); i++) {
int x = v[i];
while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
st.pop();
}
if (st.size() < k)
st.push(x);
}
while (!st.empty()) {
ret.push_back(st.top());
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
bool greater(vector<int>& a, vector<int>& b, int i, int j)
{
while (i < a.size() && j < b.size() && a[i] == b[j])
i++, j++;
return j == b.size() || (i < a.size() && a[i] > b[j]);
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
vector<int> ret;
int n = nums1.size();
int m = nums2.size();
for (int i = 0; i <= k; i++) {
if (i <= n && (k - i) <= m) {
vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
if (greater(candidate, ret, 0, 0)) {
ret = candidate;
}
}
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 };
print_vector(ob.maxNumber(v, v1, 5));
}輸入
{ 3, 4, 7, 5 }
{ 9, 1, 3, 5, 8, 4 }
5輸出
[9, 8, 7, 5, 4, ]
更新於：2020年6月1日
162 次瀏覽
廣告