LintCode-379.将数组重新排序以构造最小值
2024-08-26 17:23:07
将数组重新排序以构造最小值
给定一个整数数组，请将其重新排序，以构造最小值。
注意事项
The result may be very large, so you need to return a string instead of an integer.
样例
给定 [3, 32, 321]，通过将数组重新排序，可构造 6 个可能性数字：
3+32+321=332321
3+321+32=332132
32+3+321=323321
32+321+3=323213
321+3+32=321332
321+32+3=321323
其中，最小值为 321323，所以，将数组重新排序后，该数组变为 [321, 32, 3]。挑战
在原数组上完成，不使用额外空间。
标签
数组
code
class Solution {
public:
/**
* @param nums n non-negative integer array
* @return a string
*/
void transferToString(string &result,int number){
if(number<10) {
result+=('0'+number);
return;
}
int temp=number;
transferToString(result,number/10);
result+=('0'+temp);
}
bool compare(int num1,int num2){
string com1,com2;
if(num1==0)
com1+=('0'+num1);
while(num1) {
com1+=('0'+num1);
num1/=10;
}
if(num2==0)
com2+=('0'+num2);
while(num2) {
com2+=('0'+num2);
num2/=10;
}
int len1=com1.size(),len2=com2.size();
int i,j;
for(i=len1-1,j=len2-1;i>=0&&j>=0;i--,j--) {
if(com1[i]>com2[j])
return true;
else if(com1[i]<com2[j])
return false;
}
if(i==-1&&j==-1)
return false;
if(i==-1) {
while(j>=0) {
if(com2[j]<com2[j+1])
return true;
else if(com2[j]>com2[j+1])
return false;
else
j--;
}
return false;
}
else {
while(i>=0) {
if(com1[i]<com1[i+1])
return false;
else if(com2[i]>com2[i+1])
return true;
else
i--;
}
return false;
}
}
string minNumber(vector<int>& nums) {
// Write your code here
string result;
if(nums.empty())
return result;
int n=nums.size();
int i;
for(i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++) {
if(compare(nums[j],nums[j+1])) {
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
for(i=0;i<nums.size();i++) {
if(result.empty()&&nums[i]==0)
continue;
else
transferToString(result,nums[i]);
}
if(result.empty())
result+='0';
return result;
}
};最新文章
- 格式化 float 类型,保留小数点后1位
- HMM基本原理及其实现（隐马尔科夫模型）
- OC的runtime运行机制
- js模版引擎handlebars.js实用教程——each嵌套
- Oracle connect by 树查询之三(超详细)
- NA
- 六种流行的语言---C、C++、python、Java、php、C#比较[转]
- Android MVC模式
- 黄聪：WordPress 函数：add_filter()（添加过滤器）
- JsRender系列demo(5) for else
- Yii2的相关学习记录，alert等美化、confirm异步、session中的flash及小部件的使用（六）
- 2013 ACM/ICPC 成都网络赛解题报告
- OpenSSL命令---rand
- C/C++：多个.cpp文件包括同一个.h头文件定义方法
- 二维码(QR Code)生成与解析
- MacBook 最近发现的一些问题和技巧
- Spring Boot实战笔记（七）-- Spring高级话题（计划任务）
- Angular 6的新特性介绍
- RabbitMQ 官方demo1
- .NET扩展方法 封装公用方法