最小可用ID 算法的威力
题目：系统中每一个ID具有独特性，有些ID处于使用的状态，有些ID可以分配给新的用户，现在的问题是，怎么样找到最小的可用ID呢？
当前正在使用的ID：
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
解法一：暴力搜索
我们立即可以写出下面的解法：1
2
3
4
5
6def brute_force ( lst ):
i = 0
while True :
if i not in lst :
return i
i = i + 1
在个解法在一个几百万个ID系统中表现的性能很差，需要O(N*N)的时间。
解法二：时间优化
改进这一解法的关键基于这一事实:对于任何n个非负整数x 1 , x 2 , …, x n ,如果存在小于n的可用整数,必然存在某个x i 不在[0, n)这个范围内。否则这些整数一定是0, 1, …, n − 1的某个排列,这种情况下,最小的可用整数是n。1
2
3
4
5
6
7def min_free(A):
n = len(A)
a = [0]*(n+1)
for x in A:
if x < n:
a[x] = 1;
return a.index(0);
缺点：空间上有浪费。
解法三：分而治之
我们在速度上的改进是以空间上的消耗为代价的。由于维护了一个长度为n的标志数组,当n很大时,空间上的性能就成了新的瓶颈。分而治之的典型策略是将问题分解为若干规模较小的子问题,然后逐步解决它们以得到最终的结果。我们可以将所有满足xi ≤ ⌊n/2⌋的整数放入一个子序列A′;将剩余的其他整数放入另外一个序列A′′。根据公式1,如果序列A′ 的长度正好是⌊n/2⌋,这说明前一半的整数已经“满了”,最小的可用整数一定可以在A′′中递归地找到。否则,最小的可用整数可以在A′中找到。总之,通过这一划分,问题的规模减小了。
需要注意的是,当我们在子序列A′′ 中递归查找时,边界情况发生了一些变化,我们不再是从0开始寻找最小可用整数,查找的下界变成了⌊n/2⌋ + 1。因此我们的算法应定义为minfree(A, l, u),其中l和u分别是上下界。递归结束的边界条件是当待查找的序列变为空的时候,此时我们只需要返回下界作为结果即可。1
2
3
4
5
6
7
8
9
10
11
12
13def dc_min_free(lst):
return binary_search(lst, 0, len(lst)-1)
def binary_search(lst, l, u):
if lst == []:
return l
m = (l + u ) / 2
xs = [x for x in lst if x <= m]
ys = [x for x in lst if x > m]
if len(xs) == m - l + 1:
return binary_search(ys, m+1, u)
else:
return binary_search(xs, l, m)
时间复杂度为O(n)，空间复杂度为O(logn)。
丑数 数据结构的威力
如果说最小可用ID问题还有一些应用价值,那么接下来这个问题就纯粹是为了“有趣”了。我们要寻找第1500个“丑数”。所谓丑数,就是只含有2、3或5这三个因子的自然数。前三个丑数按照定义分别是2、3和5。数字60 = 2x2x3x5是第25个丑数。数字21 = 3x7 由于含有因子7,所以不是丑数。前10个丑数如下表:2,3,4,5,6,8,9,10,12,15
如果我们认为1也是一个合法的丑数,则1就是第一个丑数。
暴力解法
这道题目看起来并不复杂,我们可以从1开始,逐一检查所有自然数,对于每个整数,我们把所有的2、3和5的因子都除去,如果结果是1,则找到了一个丑数,当遇到第n= 1500个丑数时就找到答案了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20def valid(x):
while x%2==0:
x=x/2
while x%3==0:
x=x/3
while x%5==0:
x=x/5
if x==1:
return 1
else:
return 0
def get_number(n):
x=1
i=0
while(1):
if valid(x):
i=i+1
if i==n:
return x
x=x+1;
改进一
我们的思路是先把1作为唯一的元素放入队列,然后我们不断从队列另一侧取出元素,分别乘以2、3和5,这样就得到了3个新的元素。然后把它们按照大小顺序放入队列。注意,这样产生的整数有可能已经在队列中存在了。这种情况下,我们需要丢弃重复产生的元素。另外新产生的整数还有可能小于队列尾部的某些元素,所以我们在插入时,需要保持它们在队列中的大小顺序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int get_number(int n){
queue<int> Q;
int t;
Q.push(1);
while(n > 0){
t=Q.front();
Q.pop();
unique_enqueue(Q,2*t);
unique_enqueue(Q,3*t);
unique_enqueue(Q,4*t);
n--;
}
}
void unique_enqueue(queue<int> *Q, int x){
int i = 0;
while(i < Q->size() && Q[i] < x){
i++;
}
if(i < Q->size() && Q[i]==x){
return;
}
insert(Q,i,x);
}
改进二
我们可以用三个队列来进行改进。这三个队列表示为Q 2 ,Q 3 和Q 5 。它们初
始化为Q 2 = {2},Q 3 = {3}和Q 5 = {5}。我们每次从这三个队列的头部选择最小的一个元素x取出,然后进行下面的检查:
- 如果x是从Q2取出的,我们将2x加入Q2 ,3x加入Q3 ,5x加入Q5。
- 如果x是从Q3取出的,我们只将3x加入Q3,5x加入Q5,而不需要将2x加
入Q2。这是因为2x已经在Q3中了。 - 如果x是从Q5取出的,我们只将5x加入Q5 ,而不需要处理2x和3x了。
1 | typedef unsigned long Integer; |
改进三
首先，第一个丑数为“1”，后面的每一个丑数都是有前一个丑数乘2、3、5或7而来，那么后一个丑数就是前一个乘这四个数得到的最小值，for example：第一个：1，第二个：1*2、1*3、1*5或1*7，显然为2，第三个：2*2,1*3,1*5或1*7，显然是3，第四个：2*2,,2*3,1*5,1*7为4，第五个：3*2,2*3,1*5,1*7……
1 | int a[5850]; |
