在这个问题中,我们得到了一个数字数组,我们必须找到可以通过以某种方式更改它们而获得的最大值。安排的条件是,偶数和奇数的顺序应保持相同,即所有偶数的顺序均不可更改。
让我们举个例子来更好地理解这个概念,
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以奇数的顺序排在前面,因此我们先考虑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