[已解决]Python：每日一题 294

zltzlt

今天的题目：

给定一个未经排序的数组，请找出这个数组排序之后的两个相邻元素之间最大的间距。

注意：如果数组中少于 2 个元素，返回 0。

示例 1：

输入：[1, 9, 2, 5]
输出：4
解释：排序之后的数组是 [1, 2, 5, 9]，最大的间距是在 5 和 9 之间。

示例 2：

输入：[1]
输出：0
解释：数组中的元素少于 2 个。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2019-12-25 21:05:51

抢沙发
代码：

1. def solve(st:'list 只含整型数据的')->int:
   
2.     le = len(st)
   
3.     if le < 2:
   
4.         return 0
   
5.     st.sort()
   
6.     try:
   
7.         return max([st[x]-st[x-1] for x in range(1,le)])
   
8.     #下面的是为了防止超出内存限制的情况用的应急代码
   
9.     except MemoryError:
   
10.         m = 0
    
11.         for x in range(1,le):m = max(m,st[x]-st[x-1])
    
12.         return m
    
13. if __name__ == '__main__':
    
14.     print('示例1 输出：',solve([1, 9, 2, 5]))
    
15.     print('示例2 输出：',solve([1]))
    

复制代码

跳转到最佳答案楼层

阴阳神万物主

抢沙发
代码：

1. def solve(st:'list 只含整型数据的')->int:
   
2.     le = len(st)
   
3.     if le < 2:
   
4.         return 0
   
5.     st.sort()
   
6.     try:
   
7.         return max([st[x]-st[x-1] for x in range(1,le)])
   
8.     #下面的是为了防止超出内存限制的情况用的应急代码
   
9.     except MemoryError:
   
10.         m = 0
    
11.         for x in range(1,le):m = max(m,st[x]-st[x-1])
    
12.         return m
    
13. if __name__ == '__main__':
    
14.     print('示例1 输出：',solve([1, 9, 2, 5]))
    
15.     print('示例2 输出：',solve([1]))
    

复制代码

Unicorn#

1. def solve(nums):
   
2.     if len(nums) < 2:
   
3.         return 0
   
4.     else:
   
5.         nums.sort()
   
6.         return sorted(map(lambda x:abs(nums[x]-nums[x+1]), range(len(nums)-1)))[-1]

复制代码

塔利班

1. def fun294(x):
   
2.     if len(x)<2:
   
3.         return 0
   
4.     else:
   
5.         m=0
   
6.         x.sort()
   
7.         for i in range(len(x)-1):
   
8.             t=abs(x[i]-x[i+1])
   
9.             if t>m:
   
10.                 m=t
    
11.         return m

复制代码

先写个朴素的nlogn

闲愚

1. def func_294(s):
   
2.     result = 0
   
3.     if len(s) > 1:
   
4.         s.sort()
   
5.         for i in range(len(s) - 1):
   
6.             if result < s[i + 1] - s[i]:
   
7.                 result = s[i + 1] - s[i]
   
8.             else:
   
9.                 pass
   
10.     else:
    
11.         pass
    
12.     return result
    
13. 
    
14. if __name__ == '__main__':
    
15.     print('自测1：',func_294([1,9,2,5]))
    
16.     print('自测2：',func_294([0]))
    
17.     print('自测3：',func_294([1,1,1,1]))
    

复制代码

Croper

简单的算法（有排序，理论时间复杂度不小于O[nlogn])

1. def func294_orgin(l):
   
2.     l=list(set(l))
   
3.     l.sort()
   
4.     return 0 if len(l)<2 else max([l[i+1]-l[i] for i in range(len(l)-1)])
   

复制代码

快速的算法（好像并不快，虽然理论时间复杂度是O[n])

1. def func294(l):
   
2.     if len(n)<2:
   
3.         return 0
   
4.     lowbound=min(l)
   
5.     hibound=max(l)
   
6.     n=len(l)-1
   
7.     buck=[None]*n
   
8.     interval=(hibound-lowbound-1)//n+1
   
9.     ret=interval
   
10.     for i in l:
    
11.         if (i==hibound):
    
12.             continue;
    
13.         j=(i-lowbound)//interval
    
14.         if buck[j] is None:
    
15.             buck[j]=[i,i]
    
16.         else:
    
17.             if i<buck[j][0]:
    
18.                 buck[j][0]=i
    
19.             elif i>buck[j][1]:
    
20.                 buck[j][1]=i
    
21.     a=lowbound
    
22.     for b in buck:
    
23.         if b is None:
    
24.             continue
    
25.         if ret<b[0]-a:
    
26.             ret=b[0]-a
    
27.         a=b[1]
    
28.     if ret<hibound-a:
    
29.         ret=hibound-a
    
30.     return ret

复制代码

但是测试结果表明，算法2花费的时间大概是算法1的3倍。。，纠结

TJBEST

我感觉我的速度可能不是最快的（取决于楼主的测试序列是什么样的），因为我用了set。但是我这个去重能降低某些重复元素过多的序列的时间复杂度

1. def fun294(lst):#不排序太麻烦 任何的查找我认为不排序就是耍流氓
   
2.     if len(lst) < 2:
   
3.         return 0
   
4.     else:
   
5.         newlst = list(sorted(set(lst)))
   
6.         countlst = []
   
7.         index = 0
   
8.         maxnum = 0
   
9.         while index< len(newlst)-1:
   
10.             if maxnum < newlst[index + 1]-newlst[index]:
    
11.                 maxnum = newlst[index + 1]-newlst[index]
    
12.             index += 1
    
13.         return maxnum

复制代码

Seawolf

1. def func(num):
   
2.         if len(num) < 2 or min(num) == max(num):
   
3.             return 0
   
4.         a, b = min(num), max(num)
   
5.         size = (b-a)//(len(num)-1) or 1
   
6.         bucket = [[None, None] for _ in range((b-a)//size+1)]
   
7.         for n in num:
   
8.             b = bucket[(n-a)//size]
   
9.             b[0] = n if b[0] is None else min(b[0], n)
   
10.             b[1] = n if b[1] is None else max(b[1], n)
    
11.         bucket = [b for b in bucket if b[0] is not None]
    
12.         return max(bucket[i][0]-bucket[i-1][1] for i in range(1, len(bucket)))

复制代码

Stubborn

有考虑，再把步长拉大一点的吗？现在步长2  扩大到 3 4 5 6 。。。。

1. def fun294(array):
   
2.     if len(array) < 2: return 0
   
3.     M = 0
   
4.     array = list(sorted(set(array)))
   
5.     for i in range(1, len(array), 2):
   
6.         if i == len(array)-1:M = max(M, array[i]-array[i-1])
   
7.         else:M = max(array[i]-array[i-1], array[i+1]-array[i])
   
8.     return M

复制代码

1. 
   
2. 长度1用时 1.5400000000012626e-06 s 0
   
3. 长度10用时 1.488100000000131e-05 s 1
   
4. 长度100用时 5.747300000000233e-05 s 2
   
5. 长度1000用时 0.0005285490000000032 s 3
   
6. 长度10000用时 0.005436873999999994 s 4
   
7. 长度100000用时 0.05766370900000001 s 5
   
8. 长度1000000用时 0.7396545440000002 s 6
   
9. 长度10000000用时 8.062409364999997 s 7
   

复制代码

花里胡哨的没有鸟用~~~

1. def funcc(array):
   
2.     if len(array) < 2: return 0
   
3.     array = list(sorted(set(array)))
   
4.     return max([x-y for x,y in zip(array[1:], array)])

复制代码

凌九霄

1. def func294(L: list):
   
2.     L = sorted(L)
   
3.     return 0 if len(L) < 2 else max([L[i] - L[i - 1] for i in range(1, len(L))])

复制代码

fan1993423

1. def fun294(lst):
   
2.     if len(lst)<2:
   
3.         return 0
   
4.     else:
   
5.         lst.sort()
   
6.         return max([lst[i]-lst[i-1] for i in range(len(lst))])

复制代码

CommonName

1. t = list(set(input('请输入数组: ')))
   
2. if len(t) > 1:
   
3.     t.sort()
   
4.     r = float(t[-1]) - float(t[-2])
   
5.     print(f'结果: {r}')
   
6. else:
   
7.     print(f'结果是: {float(t[0])}')

复制代码

百分号

1. list1 =eval(input('请输入数组：'))
   
2. list2 = []
   
3. list3 = []
   
4. if len(list1) < 2:
   
5.   print(0)
   
6. else:
   
7.     list2 = sorted(list1)
   
8.     for i in range(len(list1)):
   
9.         if (i ==len(list1)-1):
   
10.             break
    
11.         else:
    
12.             ele = (list2[i+1]) - (list2[i])
    
13.             list3.append(ele)
    
14.     for j in range(len(list3)):
    
15.         if (j == 0)and (list3[j] == max(list3)):
    
16.             print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j] , list2[j+1]))
    
17.         elif (j == len(list3)-1) and (list3[j] == max(list3)):
    
18.             print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j-1] , list2[j]))
    
19.         else:
    
20.             if (list3[j] == max(list3)):
    
21.                 print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j-1] , list2[j+1]))
    
22.     print('整理之后的数组：',list2)

复制代码

kinkon

1. def fun294(n):
   
2.     k = len(n)
   
3.     if k < 2:
   
4.         return 0
   
5.     else:
   
6.         n = sorted(set(n))
   
7.         b,t = 0,-1
   
8.         for i in range(1, k//2+1):            
   
9.             a = max([n[i] - n[i-1], n[t] - n[t-1]])
   
10.             t -= 1            
    
11.             if b < a:
    
12.                 b = a            
    
13.         return b
    
14. print(fun294([1, 2, 5, 9]))
    
15. print(fun294([1]))

复制代码

1. def fun294(n):
   
2.     n = sorted(n)
   
3.     k = len(n)
   
4.     return 0 if k < 2 else max([max([n[i] - n[i-1],n[i+1] - n[i]]) for i in range(1, k-1 ,2)])

复制代码

776667

1. def fun294(x):
   
2.     x = sorted(x)
   
3.     try:
   
4.         return max([x[i]-x[i-1] for i in range(1,len(x))])
   
5.     except ValueError:
   
6.         return 0

复制代码

gufengaoyue

1. def funtest(a):
   
2.     try:
   
3.         b=sorted(set(a))
   
4.         return max([b[x]-b[x-1] for x in range(1,len(b))])
   
5.     except:
   
6.         return 0

复制代码

沙里爬

1. def solution(lst):
   
2.     lst = sorted(lst)
   
3.     lenth = len(lst)
   
4.     if lenth<2:
   
5.         return 0
   
6.     max = 0
   
7.     for i in range(1,lenth):
   
8.         if max<(lst[i]-lst[i-1]):
   
9.             max = lst[i]-lst[i-1]
   
10.     return max

复制代码

流羽星

1. def a(list_1):
   
2.     if len(list_1)<2:
   
3.         return 0
   
4.     list_1.sort()
   
5.     list_2=[]
   
6.     for i in range(1,len(list_1)):
   
7.         n=list_1[i]-list_1[i-1]
   
8.         list_2.append(n)
   
9.     return max(list_2)

复制代码

danteer

1. def fun(list1):
   
2.     list1 = list(set(list1))
   
3.     if len(list1) < 2:
   
4.         return 0
   
5.     else:
   
6.         list1.sort()
   
7.         return max([list1[i+1]-list1[i] for i in range(len(list1)-1)])

复制代码

阴阳神万物主

Stubborn 发表于 2019-12-25 22:38
有考虑，再把步长拉大一点的吗？现在步长2  扩大到 3 4 5 6 。。。。

步长还能大？但是呢，步子太大容易扯到蛋啊。