Python：每日一题 294,Python交流,技术交流,鱼C论坛

zltzlt 发表于 2019-12-25 20:58:11

Python：每日一题 294

今天的题目：

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

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

示例 1：

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

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

{:10_298:}欢迎大家一起答题！ {:10_298:}

阴阳神万物主 发表于 2019-12-25 21:05:51

本帖最后由阴阳神万物主于 2019-12-25 21:17 编辑

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

Unicorn# 发表于 2019-12-25 21:06:48

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

塔利班 发表于 2019-12-25 21:09:59

本帖最后由塔利班于 2019-12-25 21:16 编辑

def fun294(x):
if len(x)<2:
   return 0
else:
   m=0
   x.sort()
   for i in range(len(x)-1):
         t=abs(x-x)
         if t>m:
            m=t
   return m
先写个朴素的nlogn

闲愚发表于 2019-12-25 21:34:24

def func_294(s):
result = 0
if len(s) > 1:
   s.sort()
   for i in range(len(s) - 1):
         if result < s - s:
            result = s - s
         else:
            pass
else:
   pass
return result

if __name__ == '__main__':
print('自测1：',func_294())
print('自测2：',func_294())
print('自测3：',func_294())

Croper 发表于 2019-12-25 21:40:41

本帖最后由 Croper 于 2019-12-25 22:35 编辑

简单的算法（有排序，理论时间复杂度不小于O)def func294_orgin(l):
l=list(set(l))
l.sort()
return 0 if len(l)<2 else max(-l for i in range(len(l)-1)])

快速的算法（好像并不快，虽然理论时间复杂度是O)
def func294(l):
if len(n)<2:
   return 0
lowbound=min(l)
hibound=max(l)
n=len(l)-1
buck=*n
interval=(hibound-lowbound-1)//n+1
ret=interval
for i in l:
   if (i==hibound):
         continue;
   j=(i-lowbound)//interval
   if buck is None:
         buck=
   else:
         if i<buck:
            buck=i
         elif i>buck:
            buck=i
a=lowbound
for b in buck:
   if b is None:
         continue
   if ret<b-a:
         ret=b-a
   a=b
if ret<hibound-a:
   ret=hibound-a
return ret

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

TJBEST 发表于 2019-12-25 21:57:45

本帖最后由 TJBEST 于 2019-12-25 23:18 编辑

我感觉我的速度可能不是最快的（取决于楼主的测试序列是什么样的），因为我用了set。但是我这个去重能降低某些重复元素过多的序列的时间复杂度
def fun294(lst):#不排序太麻烦任何的查找我认为不排序就是耍流氓
if len(lst) < 2:
   return 0
else:
   newlst = list(sorted(set(lst)))
   countlst = []
   index = 0
   maxnum = 0
   while index< len(newlst)-1:
         if maxnum < newlst-newlst:
            maxnum = newlst-newlst
         index += 1
   return maxnum

Seawolf 发表于 2019-12-25 22:31:17

def func(num):
   if len(num) < 2 or min(num) == max(num):
         return 0
   a, b = min(num), max(num)
   size = (b-a)//(len(num)-1) or 1
   bucket = [ for _ in range((b-a)//size+1)]
   for n in num:
         b = bucket[(n-a)//size]
         b = n if b is None else min(b, n)
         b = n if b is None else max(b, n)
   bucket = is not None]
   return max(bucket-bucket for i in range(1, len(bucket)))

Stubborn 发表于 2019-12-25 22:38:52

本帖最后由 Stubborn 于 2019-12-26 17:12 编辑

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

def fun294(array):
if len(array) < 2: return 0
M = 0
array = list(sorted(set(array)))
for i in range(1, len(array), 2):
if i == len(array)-1:M = max(M, array-array)
else:M = max(array-array, array-array)
return M

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

花里胡哨的没有鸟用~~~
def funcc(array):
if len(array) < 2: return 0
array = list(sorted(set(array)))
return max(, array)])

凌九霄 发表于 2019-12-25 23:12:04

本帖最后由凌九霄于 2019-12-25 23:14 编辑

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

fan1993423 发表于 2019-12-25 23:14:54

本帖最后由 fan1993423 于 2019-12-25 23:17 编辑

def fun294(lst):
if len(lst)<2:
   return 0
else:
   lst.sort()
   return max(-lst for i in range(len(lst))])

CommonName 发表于 2019-12-26 00:57:16

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

百分号 发表于 2019-12-26 02:57:41

list1 =eval(input('请输入数组：'))
list2 = []
list3 = []
if len(list1) < 2:
print(0)
else:
list2 = sorted(list1)
for i in range(len(list1)):
   if (i ==len(list1)-1):
         break
   else:
         ele = (list2) - (list2)
         list3.append(ele)
for j in range(len(list3)):
   if (j == 0)and (list3 == max(list3)):
         print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2 , list2))
   elif (j == len(list3)-1) and (list3 == max(list3)):
         print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2 , list2))
   else:
         if (list3 == max(list3)):
            print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2 , list2))
print('整理之后的数组：',list2)

kinkon 发表于 2019-12-26 09:18:25

本帖最后由 kinkon 于 2019-12-26 14:06 编辑

def fun294(n):
k = len(n)
if k < 2:
   return 0
else:
   n = sorted(set(n))
   b,t = 0,-1
   for i in range(1, k//2+1):
         a = max( - n, n - n])
         t -= 1
         if b < a:
            b = a
   return b
print(fun294())
print(fun294())

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

776667 发表于 2019-12-26 10:24:27

def fun294(x):
x = sorted(x)
try:
return max(-x for i in range(1,len(x))])
except ValueError:
return 0

gufengaoyue 发表于 2019-12-26 10:40:16

def funtest(a):
try:
   b=sorted(set(a))
   return max(-b for x in range(1,len(b))])
except:
   return 0

沙里爬 发表于 2019-12-26 10:50:17

def solution(lst):
lst = sorted(lst)
lenth = len(lst)
if lenth<2:
   return 0
max = 0
for i in range(1,lenth):
   if max<(lst-lst):
         max = lst-lst
return max

流羽星 发表于 2019-12-26 12:32:41

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

danteer 发表于 2019-12-26 13:10:47

本帖最后由 danteer 于 2019-12-26 20:00 编辑

def fun(list1):
list1 = list(set(list1))
if len(list1) < 2:
   return 0
else:
   list1.sort()
   return max(-list1 for i in range(len(list1)-1)])

阴阳神万物主 发表于 2019-12-26 14:18:10

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

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

页: [1] 2

鱼C论坛's Archiver

Python：每日一题 294