Python实现无重复数字

当我们想要取的一些不重复的数字时,通常我们会想到random.sample方法

1
2
3
4
import random

print(random.sample(range(0, 10), 4))
# [5, 1, 0, 2]

但是这样只能保证每次运行这行代码时的数字是不重复的,如果要多次运行上面的代码就会有重复的数字出现。

最先想到的方法就是将每次取到数字都放在一个set内,每次产生新的随机数字时,先判断它是否在这个set内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import random
import functools
import time


def scale_time(fn):
functools.wraps(fn)

def wrapper(*args, **kw):
start_time = time.time()
result = fn(*args, **kw)
end_time = time.time()
print(f"{end_time - start_time}")
return result

return wrapper


@scale_time
def test():
result_set = set()

while len(result_set) < 9999:
_data = random.sample(range(0, 10000), 1)
result_set = result_set | set(_data)


test()
# 6.2531819343566895

从上面代码可以看到,这种方式效率是比较低的,越到后面,产生不重复随机数的概率就会越来越低,就需要重试更多的次数

有没有优化的方式呢?那就是下面要讲的,利用列表来取不重复的随机数,每次取出来的随机数都能保证和之前取出来的不重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random
import functools
import time


def scale_time(fn):
functools.wraps(fn)

def wrapper(*args, **kw):
start_time = time.time()
result = fn(*args, **kw)
end_time = time.time()
print(f"{end_time - start_time}")
return result

return wrapper


@scale_time
def test():
result_set = set()
data = list(range(0, 10000))

while len(result_set) < 9999:
_data = random.randint(0, len(data)-1)
result_set.add(data[_data])
data.pop(_data)

test()
# 0.027987957000732422

上面的代码会pop原来数组的值,如果要继续优化,可以不pop,而是修改元素的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import random
import functools
import time


def scale_time(fn):
functools.wraps(fn)

def wrapper(*args, **kw):
start_time = time.time()
result = fn(*args, **kw)
end_time = time.time()
print(f"{end_time - start_time}")
return result

return wrapper


@scale_time
def test():
result_set = set()
data = list(range(0, 10000))

_index = len(data) - 1
while len(result_set) < 9999:
_data = random.randint(0, _index)
result_set.add(data[_data])
_index -= 1
data[-len(result_set)], data[_data] = data[_data], data[-len(result_set)]

test()
# 0.02704787254333496