C++程序 将给定数字排列成最大的数字

C++程序 将给定数字排列成最大的数字

给定一个由数字组成的数组,请以能生成最大值的方式排列它们。例如,如果给定的数字是{54,546,548,60},则排列6054854654生成最大值。如果给定数字是{1,34,3,98,9,76,45,4},则排列998764543431生成最大值。

我们首先想到的 简单的解决方案 是按降序对所有数字进行排序,但简单的排序不起作用。例如,548大于60,但在输出中60在548之前。作为第二个示例,98大于9,但是在输出中9在98之前。

那么我们该如何去做呢?想法是使用任何基于比较的排序算法。

在使用的排序算法中,可以编写一个比较函数 myCompare() 来代替默认比较,并用它来排序数字。

给定两个数字 XYmyCompare() 应该决定首先放置哪个数字 – 我们比较两个数字XY(Y添加到X的末尾)和YX(X添加到Y的末尾)。如果 XY 更大,那么在输出中应该先放X,否则应该先放Y。例如,假设X和Y分别为542和60。为了比较X和Y,我们比较54260和60542。由于60542大于54260,我们首先放置Y。

以下是上述方法的实现。

为了使代码简单,数字被视为字符串,使用向量而不是正常数组。

下面是上述方法的实现:

// Given an array of numbers,
// program to arrange the numbers
// to form the largest number
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
  
// A comparison function which 
// is used by sort() in
// printLargest()
int myCompare(string X, string Y)
{
    // first append Y at the end of X
    string XY = X.append(Y);
  
    // then append X at the end of Y
    string YX = Y.append(X);
  
    // Now see which of the two 
    // formed numbers is greater
    return XY.compare(YX) > 0 ? 1 : 0;
}
  
// The main function that prints 
// the arrangement with the
// largest value. The function 
// accepts a vector of strings
void printLargest(vector<string> arr)
{    
    // Sort the numbers using 
    // library sort function. The
    // function uses our comparison 
    // function myCompare() to
    // compare two strings. See
    // http://www.cplusplus.com/reference/
    // algorithm/sort/
    // for details
    sort(arr.begin(), arr.end(), myCompare);
  
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];
}
  
// Driver code
int main()
{
    vector<string> arr;
  
    // output should be 6054854654
    arr.push_back("54");
    arr.push_back("546");
    arr.push_back("548");
    arr.push_back("60");
    printLargest(arr);
  
    return 0;
}  

输出:

6054854654

时间复杂度: O(nlogn) , sorting 被认为具有O(nlogn)的运行时间复杂度,for循环在O(n)时间内运行。

辅助空间: O(1)。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例