剑指offer—把数组排成最小的数

2024-04-04 18:08

文章标签 数组最小 offer 排成

本文主要是介绍剑指offer—把数组排成最小的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

我们可以采用贪心算法的思想：两两最小，总和最小。先两个数两个数的比较，让这两个数排起来最小，然后通过冒泡排序的方法把所有数都两两比较一遍，最后组合出来的数就是最小的。所有整个过程分为三步：让两个数排起来最小，通过冒泡排序让所有数都排起来最小，最后拼接为一个数字返回。
1.让两个数排起来最小。
我们可以通过将数字转换为字符串变量，然后通过字符串拼接的方法来实现。这样就避免了需要考虑数字的位数问题。Int型变量可以通过stringstrem来转换为string变量：

string int2sting(int n)
{string res;stringstream ss;ss<<n;ss>>res;return res;
}

在转换完之后通过字符串拼接的方式来比较两个数的两种排列方式，哪种最小：

 string s1=num2string [j]+num2string [j+1];string s2=num2string [j+1]+num2string [j];if(s1>s2){string temp=num2string [j];num2string [j]=num2string [j+1];num2string [j+1]=temp;}

2.通过冒泡排序来让所有的数都两两比较

for(int k=num2string .size()-1;k>=0;--k)for(int j=0;j<k;++j){string s1=num2string [j]+num2string [j+1];string s2=num2string [j+1]+num2string [j];if(s1>s2){string temp=num2string [j];num2string [j]=num2string [j+1];num2string [j+1]=temp;}}

3.将数组中的数组合在一起，得到可拼接的最小数

for(int i=0;i<num2string .size ();++i)res+=num2string [i];

完整程序如下：

string int2sting(int n)
{string res;stringstream ss;ss<<n;ss>>res;return res;
}
string PrintMinNumber(vector<int> numbers) {vector<string> num2string;for(int i=0;i<numbers.size ();++i){string s=int2sting (numbers[i]);num2string .push_back (s);}for(int k=num2string .size()-1;k>=0;--k)for(int j=0;j<k;++j){string s1=num2string [j]+num2string [j+1];string s2=num2string [j+1]+num2string [j];if(s1>s2){string temp=num2string [j];num2string [j]=num2string [j+1];num2string [j+1]=temp;}}string res;if(num2string .size()==0)return res;for(int i=0;i<num2string .size ();++i)res+=num2string [i];return res;}