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

2016/05/24 C和C++基础

题目描述

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string convertStr(int num){
	string str;
	while(num>0){
		int n=num/10;
		char c=(num-n*10)+'0';
		str.push_back(c);
		num=n;
	}
	string strnew(str.rbegin(),str.rend());
	return strnew;
}

int cmpStr(string str1,string str2){
	string s1=str1+str2;
	string s2=str2+str1;
	int len=s1.size();
	for(int i=0;i<len;i++){
		if(s1[i]>s2[i])
			return 1;
		else if(s1[i]<s2[i])
			return -1;
	}
	return 0;
}

string PrintMinNumber(vector<int> numbers){
	int len=numbers.size();
	if(len==0) return "";
	if(len==1) return convertStr(numbers[0]);
	vector<string> vec;
	for(int i=0;i<len;i++)
		vec.push_back(convertStr(numbers[i]));
	string str;
	for(int i=0;i<len-1;i++){                         //冒泡排序
		for(int j=0;j<len-1-i;j++){
			if(cmpStr(vec[j],vec[j+1])==1){
				string temp=vec[j];
				vec[j]=vec[j+1];
				vec[j+1]=temp;
			}
		}
	}
	for(int i=0;i<len;i++)
		str=str+vec[i];
	return str;
}

int main(){
	//int a[3]={3,32,321};
	//int a[5]={3,5,1,4,2};
	//int a[3]={3,323,32123};
	int a[2]={2,1};
	vector<int> numbers(a,a+2);
	cout<<PrintMinNumber(numbers)<<endl;
	system("pause");
}

Search

    Post Directory