【算法】数字序列中某一位的数字,把数组排成最小的数

本文主要是介绍【算法】数字序列中某一位的数字,把数组排成最小的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试题44:数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数求任意位对应的数字。

每次跳过一片数字海，每个数字海都是位数一样的数字组成的，这些数字有多少可以算出来。跳不出去时就在这片海里，因为位数都一样，也可以很容易的跳过一些数，确定在某个数字的某一位上。

#include<bits/stdc++.h>
using namespace std;int countOfIntegers(int digits);
int digitAtIndex(int index, int digits);
int beginNumber(int digits);//输入位数index,在数字序列中找出第index数字并返回 
int digitAtIndex(int index) {if(index < 0)//输入合法性检查 return -1;int digits = 1;//当前这一族数的位数,开始是1位数 while(true) {int numbers = countOfIntegers(digits);//计算digits位的数有多少个 if(index < numbers * digits)//如果剩下的index不超过这族数字海//那么就是digits位一族的数字海向后走index位return digitAtIndex(index, digits);//调用函数寻找并返回 //运行至此,没有走if,说明已经走出了这族数字海 index -= digits * numbers;//所剩index=原index-这族数字海的数字数目 digits++;//下轮检查的位数+1}//程序无法运行到这里,但为了满足int返回值 return -1;
}//计算digits位一族的数字海中有多少数字 
int countOfIntegers(int digits) {if(digits == 1)//一位数有10个 return 10;//两位数有99-10+1=90个;三位数有999-100+1=900个;四位数有9000个... int count = (int) pow(10, digits - 1);return 9 * count;//即9*10^(digits-1)个数字 
}//计算返回digits位一族的数字海向后走index位
int digitAtIndex(int index, int digits) {//先从起始数字开始,向后走index/digits个真实的数字int number = beginNumber(digits) + index / digits;//然后面对的这个数就包含了要找的位 //计算一下它在这个数上是从右往左的第几位//即每个数的位数,减去index的余数 int indexFromRight = digits - index % digits;//将这个数取出来,先把它后面的数用自除去掉 for(int i = 1; i < indexFromRight; ++i)number /= 10;return number % 10;//然后这个个位就是所求了 
}//计算digits位数字海的第一个数(不是第一位数) 
int beginNumber(int digits) {if(digits == 1)//1位数字海第一个数是0 return 0;//2位是10,3位是100,4位是1000... return (int) pow(10, digits - 1);
}int main(){cout<<digitAtIndex(1001)<<endl;return 0;
}

面试题45:把数组排成最小的数

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

本质就是找到能判断两个数哪个该排在前面的排序规则，即一个有传递性的比较规则，本题使用字符串大小比较即可。书上有严格证明。\

对于两个数m和n，只要比较其字符串形式的连接mn和nm哪个小即可。

#include<bits/stdc++.h>
using namespace std;int compare(const void* strNumber1, const void* strNumber2);//int型整数用十进制表示最多只有10位
const int g_MaxNumberLength = 10;//存[m][n]的字符串 
char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];
//存[n][m]的字符串 
char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];//给出整形数组和数组长度,输出排成的最小的数 
void PrintMinNumber(const int* numbers, int length) {if(numbers == nullptr || length <= 0)//数组非空校验 return;//存储若干char数组,所需空间和输入的整形数组一样 char** strNumbers = (char**)(new int[length]);//对于这length个数 for(int i = 0; i < length; ++i) {//每个数分配一个char类型数组存储,+1是为了存'\0' strNumbers[i] = new char[g_MaxNumberLength + 1];//将输入的对应位置的整数写入相应的字符串中 sprintf(strNumbers[i], "%d", numbers[i]);}//对strNumbers中的元素(是char数组)进行排序//传入自定义的compare函数指针以确定排序的方法 qsort(strNumbers, length, sizeof(char*), compare);//排好序后,按顺序将其输出即可 for(int i = 0; i < length; ++i)printf("%s", strNumbers[i]);printf("\n");//释放堆空间 for(int i = 0; i < length; ++i)delete[] strNumbers[i];delete[] strNumbers;
}//如果[strNumber1][strNumber2] > [strNumber2][strNumber1],返回值大于0
//如果[strNumber1][strNumber2] = [strNumber2][strNumber1],返回值等于0
//如果[strNumber1][strNumber2] < [strNumber2][strNumber1],返回值小于0
int compare(const void* strNumber1, const void* strNumber2) {//[strNumber1][strNumber2]就是先拷贝1再连接2 strcpy(g_StrCombine1, *(const char**)strNumber1);strcat(g_StrCombine1, *(const char**)strNumber2);//[strNumber2][strNumber1]就是先拷贝2再连接1strcpy(g_StrCombine2, *(const char**)strNumber2);strcat(g_StrCombine2, *(const char**)strNumber1);//直接调用字符串比较的函数 return strcmp(g_StrCombine1, g_StrCombine2);
}int main(){int numbers[]={3,32,321};PrintMinNumber(numbers,sizeof(numbers)/sizeof(int));return 0;
}