【面试题】比给定数大的最小数

今天在全新整理：微软、谷歌、百度等公司经典面试100题[第101-160题]看到一道挺常见的题，这里面说是Google2009华南地区笔试题，原题如下。

给定一个集合A=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。

比如，A=[1,0] ，K=21，那么输出结果应该为100。

这种输出比给定数大的最小数的题还是很常见的，不记得有没写过了。。有几天没写程序了，恢复一下感觉，写了一下，针对这道题的解法。

因为元素只有 0 到 9 且不止是否有序是否有重复，所以先哈希了一下集合 A 中的元素，哈希到 numTab 里面，0 表示没这个数，大于 0 表示有这个数，同时记下 A 中的最小值 min 和次小值 secMin。

然后对 numTab 做了一下处理，这个数组第 i 个元素表示，集合 A 中大于等于 i 的最小值是多少，为 0 表示集合 A 中没有大于等于 i 的数。

这样从最后一位看给定的数 num，有比这一位大的就可以计算一下直接返回了，没有的话就把这一位置成最小值 min，再看前一位，一直到最高位，若一直没有返回，则说明比给定数大的最小数要比 num 多一位，也可以方便计算并返回。

其实还是代码这种语言解释这种事情会比较直接。

 1 int biggerMinNum(int *arr, int len, int num)
 2 {
 3     int min = arr[0];
 4     int secMin = 0x7FFFFFFF;
 5     int numTab[10];
 6     memset(numTab, 0, 10*sizeof(int));
 7     for(int i = 0; i < len; ++i)
 8     {
 9         numTab[arr[i]] = arr[i];
10         min = arr[i] < min ? arr[i] : min;
11     }
12     for(int i = 1; i < 10; ++i)
13     {
14         if(numTab[i] == 1 && i != min)
15         {
16             secMin = i;
17             break;
18         }
19     }
20     for(int i = 8; i >= 0; --i)
21     {
22         if(numTab[i] == 0)
23             numTab[i] = numTab[i+1];
24     }
25     int ifactor = 1;
26     int low = 0;
27     while(num/ifactor)
28     {
29         int tmp = num/ifactor;
30         tmp %= 10;
31         if(tmp < 9 && numTab[tmp+1] > tmp)
32             return (num/ifactor/10*10+numTab[tmp+1])*ifactor+low;
33         ifactor *= 10;
34         low = low*10 + min;
35     }
36     return secMin*ifactor+low;
37 }

【面试题】比给定数大的最小数

推荐阅读