记某面试题目：
输入为正整数数组，找出排好序的数组的所有连续区间， 如果该连续空间只有一个数字，将该数字放入一个数组中，否则将该连续空间的首位数字计入一个数组中，输出所有这些数组组成的数组
例如：
输入->[4,8,1,2,7,5,9,11]
输出->[[1,2],[4,5],[7,9],[11]] 7-8-9为连续空间，那么记为[7,9]
目前想出的两种解决办法：
- 先将数组排序，然后遍历数组
- 找出数组的最小值和最大值，用哈希表存储在原数组中出现的数，然后遍历最小值到最大值中间的所有数值
比较了一下效率好像差不多，期待更加优秀的解法
import random
import time
import matplotlib.pyplot as plt
random.seed(2020)
def func(nums):
if not nums: return []
nums.sort()
ans,tmp = [],[nums[0],]
for i in range(1,len(nums)):
if nums[i] != nums[i-1] + 1:
if len(tmp)==1:
ans.append([tmp[0]])
else:
ans.append([tmp[0],tmp[-1]])
tmp = []
tmp.append(nums[i])
if len(tmp)==1:
ans.append([tmp[0]])
else:
ans.append([tmp[0],tmp[-1]])
return ans
def func2(nums):
minv, maxv = float('inf'),float('-inf')
dic = {}
for i in range(len(nums)):
dic[nums[i]] = 0
if nums[i] > maxv:
maxv = nums[i]
if nums[i] < minv:
minv = nums[i]
ans,tmp = [],[]
for num in range(minv,maxv+1):
if num in dic:
tmp.append(num)
else:
if tmp:
if len(tmp)==1:
ans.append([tmp[0]])
else:
ans.append([tmp[0],tmp[-1]])
tmp = []
return ans
rounds = [50,100,500,1000,5000,10000,20000]
func1_times = []
func2_times = []
for r in rounds:
arr = []
number = 0
while len(arr) < r:
x = random.randint(1,1.2*r)
if x not in arr:
arr.append(x)
start1 = time.perf_counter()
func(arr)
end1 = time.perf_counter()
func1_times.append((end1-start1)*1000)
start2 = time.perf_counter()
func2(arr)
end2 = time.perf_counter()
func2_times.append((end2-start2)*1000)
print('test for {} rounds over'.format(r))
plt.plot(rounds,func1_times,color='b',label='common')
plt.plot(rounds,func2_times,color='r',label='hash')
plt.legend()
WX20201020-175157@2x.png
