ในโจทย์นี้ เราได้รับอาร์เรย์ของตัวเลข และเราต้องหาค่าที่ใหญ่ที่สุดที่สามารถสร้างได้โดยการจัดเรียงพวกมันในลำดับเฉพาะ เงื่อนไขคือ ลำดับของเลขคู่และเลขคี่ต้องคงที่เดิม คือ ลำดับของเลขคู่ทั้งหมดไม่สามารถเปลี่ยนแปลงได้
มาดูตัวอย่างเพื่อเข้าใจแนวคิดให้ดีขึ้น
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
เนื่องจากเราเข้าใจปัญหาแล้ว ลองสร้างวิธีแก้ปัญหา ที่นี่เราไม่สามารถเรียงลำดับแบบ descending แบบคลาสสิกได้ เนื่องจากมีเงื่อนไขเกี่ยวกับลำดับของเลขคู่และคี่ จึงต้องรักษาลำดับนี้และตรวจสอบว่าตัวแรกของลำดับเลขคู่และคี่ ไหนทำให้ได้ตัวเลขใหญ่กว่า และทำต่อไปเช่นนั้น มาดูอัลกอริทึมที่จะทำให้ชัดเจนขึ้น
อัลกอริทึม
ขั้นตอนที่ 1 : สร้างโครงสร้างสองชุด หนึ่งสำหรับเลขคู่ อีกชุดสำหรับเลขคี่ เพื่อรักษาลำดับ ขั้นตอนที่ 2 : นำสมาชิกหนึ่งจากแต่ละโครงสร้างมาเปรียบเทียบว่าการรวมกันแบบไหนให้ตัวเลขใหญ่กว่า ตัวอย่าง ถ้า E คือเลขคู่ และ O คือเลขคี่ ที่อยู่บนสุดของโครงสร้าง เราจะตรวจสอบว่า EO และ OE ไหนมากกว่า ขั้นตอนที่ 3 : นำชุดที่ใหญ่กว่าไปวางในลำดับสุดท้าย ขั้นตอนที่ 4 : พิมพ์ลำดับสุดท้าย
ตัวอย่าง
ตอนนี้ มาสร้างโปรแกรมตามอัลกอริทึมนี้
#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
