資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律學透過特定順序排列數字得到最大數 (C++)
在這個問題中，我們得到一個數字陣列，需要找到透過特定方式排列這些數字後能夠得到的最大值。排列條件是：偶數和奇數的順序必須保持不變，即所有偶數的順序不能改變。
讓我們透過一個例子來更好地理解這個概念：
Input : {17, 80, 99, 27, 14 , 22}
Output: 801799271422
Explanation: the order of Even and Odd numbers is :
Even : 80 14 22
Odd : 17 99 27這裡 99 是最大的數字，但是 17 在奇數序列中排在 99 之前，所以我們先考慮 80，然後按順序排列，例如：**80 17 99 27 14 22**
既然我們已經理解了這個問題，讓我們嘗試為其找到解決方案。由於定義了奇偶數序列的約束，我們不能採用經典的降序排列方法。我們需要保持這個序列，並檢查奇偶數序列中第一個元素的最大值，然後以此類推。讓我們來看一個演算法，這會使問題更加清晰。
演算法
Step 1 : Create two structures, one for even other for odd, this will maintain the sequence. Step 2 : Take one element from each structure and check which combination makes a large number. Example, if E is the even number and O is the odd number which are at the top of the structure. then we will check which one is Greater of EO and OE. Step 3 : Place the greater combination into the final sequence. Step 4 : Print the final sequence.
示例
現在，讓我們根據這個演算法建立一個程式。
#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
int n1 = arr1.size();
int n2 = arr2.size();
int i = 0, j = 0;
string big = "";
while (i < n1 && j < n2) {
if ((arr1[i]+arr2[j]).compare((arr2[j]+arr1[i])) > 0)
big += arr1[i++];
else
big += arr2[j++];
}
while (i < n1)
big += arr1[i++];
while (j < n2)
big += arr2[j++] ;
return big;
}
string largestNumber(vector<string> arr, int n) {
vector<string> even, odd;
for (int i=0; i<n; i++) {
int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
if (lastDigit % 2 == 0)
even.push_back(arr[i]);
else
odd.push_back(arr[i]);
}
string biggest = merge(even, odd);
return biggest;
}
int main() {
vector<string> arr;
arr.push_back("17");
arr.push_back("80");
arr.push_back("99");
arr.push_back("27");
arr.push_back("14");
arr.push_back("22");
int n = arr.size();
cout<<"Biggest possible number from the array is = "<<largestNumber(arr, n);
return 0;
}輸出
Biggest possible number from the array is = 801799271422
更新於：2019年11月22日
瀏覽量：136
廣告