时间戳

首页 > 解决方案 > 排序得到最大数

c++ - 排序得到最大数

问题描述

给定一个非负整数列表，我必须对它们进行排列，使它们在词法连接时形成最大的数字，并将结果数字作为字符串返回。

输入为：[3, 30, 34, 5, 9]

我试图手动遍历数组，但我不明白我错在哪里。所有元素都按我的预期交换，但 3 和 30 没有交换。谁能找到代码中的错误？

#include <iostream>
#include <vector>

int main(){
    std::vector<int>b={ 3, 30, 34, 5, 9 };



    for(int i=0 ;i<b.size()-1; i++){//i moves from 0 to 3 and picks the ith element
        for(int j=i+1; j<b.size(); j++){
           /*j moves from i+1 to 4 and compares  
            the strings formed by appending int turned strings b[i] and b[j] 
            in two possible orders such as "b[i]b[j]" and "b[j]b[i]"
           */

            std::string str1,str2,str3,str4;

            str1 = to_string(b[i]);
            str2 = to_string(b[j]);
            str3 = str1.append(str2);
            str4 = str2.append(str1);

            if(stoi(str4)>stoi(str3)){
           // if loop swaps if "b[j]b[i]" is greater than "b[i]b[j]"
                swap(b[i],b[j]);
            }
        }
    }
    std::string s="";
    for(int i=0; i<b.size(); i++){//creates string s from sorted array
        s.append(to_string(b[i]));
    }
    std::cout<<s;/*prints largest string that is possible by sorting the elements of array*/

    return 0;
}

预期：9534330
实际：9534303

标签： c++c++11

解决方案

你的错误是你，swap(b[i],b[j]);但你比较A的值。很快，A和B数组就变得不相关了。只需使用一个数组。交换您从中比较值的同一数组。

它会起作用的。令人惊讶的是，这种方法感觉有点令人费解，但确实如此。

编辑：

还，

   str1.append(str2);
   str2.append(str1);

不要做你认为/期望它做的事情。第一行修改str1. 你需要解决这个问题，但我不会做你的全部作业。

推荐阅读