[已解决]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

抢沙发
代码：

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

跳转到最佳答案楼层

阴阳神万物主

抢沙发
代码：

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

Unicorn#

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

塔利班

def fun294(x):
    if len(x)<2:
        return 0
    else:
        m=0
        x.sort()
        for i in range(len(x)-1):
            t=abs(x[i]-x[i+1])
            if t>m:
                m=t
        return m

先写个朴素的nlogn

闲愚

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

if __name__ == '__main__':
    print('自测1：',func_294([1,9,2,5]))
    print('自测2：',func_294([0]))
    print('自测3：',func_294([1,1,1,1]))

Croper

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

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

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

def func294(l):
    if len(n)<2:
        return 0
    lowbound=min(l)
    hibound=max(l)
    n=len(l)-1
    buck=[None]*n
    interval=(hibound-lowbound-1)//n+1
    ret=interval
    for i in l:
        if (i==hibound):
            continue;
        j=(i-lowbound)//interval
        if buck[j] is None:
            buck[j]=[i,i]
        else:
            if i<buck[j][0]:
                buck[j][0]=i
            elif i>buck[j][1]:
                buck[j][1]=i
    a=lowbound
    for b in buck:
        if b is None:
            continue
        if ret<b[0]-a:
            ret=b[0]-a
        a=b[1]
    if ret<hibound-a:
        ret=hibound-a
    return ret

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

TJBEST

我感觉我的速度可能不是最快的（取决于楼主的测试序列是什么样的），因为我用了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[index + 1]-newlst[index]:
                maxnum = newlst[index + 1]-newlst[index]
            index += 1
        return maxnum

Seawolf

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 = [[None, None] for _ in range((b-a)//size+1)]
        for n in num:
            b = bucket[(n-a)//size]
            b[0] = n if b[0] is None else min(b[0], n)
            b[1] = n if b[1] is None else max(b[1], n)
        bucket = [b for b in bucket if b[0] is not None]
        return max(bucket[i][0]-bucket[i-1][1] for i in range(1, len(bucket)))

Stubborn

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

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[i]-array[i-1])
        else:M = max(array[i]-array[i-1], array[i+1]-array[i])
    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([x-y for x,y in zip(array[1:], array)])

凌九霄

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

fan1993423

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

CommonName

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[0])}')

百分号

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[i+1]) - (list2[i])
            list3.append(ele)
    for j in range(len(list3)):
        if (j == 0)and (list3[j] == max(list3)):
            print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j] , list2[j+1]))
        elif (j == len(list3)-1) and (list3[j] == max(list3)):
            print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j-1] , list2[j]))
        else:
            if (list3[j] == max(list3)):
                print('最大的间距是%d,在%d与%d之间'%(max(list3) ,list2[j-1] , list2[j+1]))
    print('整理之后的数组：',list2)

kinkon

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[i] - n[i-1], n[t] - n[t-1]])
            t -= 1            
            if b < a:
                b = a            
        return b
print(fun294([1, 2, 5, 9]))
print(fun294([1]))

def fun294(n):
    n = sorted(n)
    k = len(n)
    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

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

gufengaoyue

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

沙里爬

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[i]-lst[i-1]):
            max = lst[i]-lst[i-1]
    return max

流羽星

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[i]-list_1[i-1]
        list_2.append(n)
    return max(list_2)

danteer

def fun(list1):
    list1 = list(set(list1))
    if len(list1) < 2:
        return 0
    else:
        list1.sort()
        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 。。。。

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