排列给定的数字以形成最大的数字？

此处我们将了解如何通过重新排列给定的数字来生成最大的数字。假设给定了{45、74、23}，该程序将找到最大数字，即 744523。所以每个数字将不会被单独排列，而是整个数字将被放置在最大数字的位置。

为了解决此问题，我们将使用字符串排序。但比较逻辑是不同的。比较函数将使用两个数字 a 和 b，然后将它们连接起来形成 ab 和 ba。其中哪个更大，则认为是那个。

算法

比较字符串 (a, b)

begin
   ab := concatenate b with a
   ba := concatenate a with b
   compare ba with ab, then return 1 if ba is bigger, otherwise return 0
end
getLargest(arr):
begin
   sort the arr with the comparison logic using compareString()
   for each string s in arr, do
      print s
   done
end

示例

 动态演示

#include<iostream>
#include <string>
#include &t;vector>
#include <algorithm>
using namespace std;
int stringCompare(string a, string b) {
   string ab = a.append(b);
   string ba = b.append(a);
   return ab.compare(ba) > 0 ? 1: 0;
}
void getLargest(vector<string> arr) {
   sort(arr.begin(), arr.end(), stringCompare); //sort the array
   for (int i =0; i < arr.size() ; i++ )
      cout << arr[i];
}
int main() {
   vector<string> arr;
   arr.push_back("45");
   arr.push_back("74");
   arr.push_back("23");
   getLargest(arr);
}

输出

744523

更新于: 2019 年 7 月 30 日

207 次浏览

开启你的 职业

完成课程获得认证

获取开始
广告