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

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

  • 题目描述

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

  • 题目解析

初次遇见这道题目，有点懵，不造该如何下手。因为无论如何都不太好比较啊，而且数字的位数也不太一样。

怎么都没有想到书上给出的正确思路这里，把数字转成字符串，然后比较字符串大小。。

果然思维还是不够发散啊。。too naive。。

  1. class Solution {
  2. public:
  3.     string PrintMinNumber(vector<int> numbers) {
  4. 		string r;
  5. 		vector<string> sr;
  6. 		for (int i = 0; i < numbers.size(); i++){
  7. 			sr.push_back(numToString(numbers[i]));
  8. 		}
  9. 		sort(sr.begin(), sr.end(), compare);
  10. 		for (int i = 0; i<sr.size(); i++)
  11. 			r += sr[i];
  12. 		return r;
  13. 	}
  14. 	string numToString(int n){
  15. 		return (n>9 ? numToString(n / 10) : "") + char(n % 10 + '0');
  16. 	}
  17. 	static bool compare(const string &a, const string &b){
  18. 		return a + b <= b + a;
  19. 	}
  20. };
弹钢琴的猫 /
Published under (CC) BY-NC-SA in categories 算法  tagged with 剑指offer  Array  String