相邻最大差值

[编程题]相邻最大差值

热度指数：17438 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。

给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。

测试样例：

[9,3,1,10],4

返回：6

算法知识视频讲解

Python

习惯不曾习惯的习惯0

这道题目有问题到底是排序后时间复杂度为0（n）还是排序前

# -*- coding:utf-8 -*-

class MaxDivision:
    def findMaxDivision(self, A, n):
        # write code here
        if len(A)==2:
            return A[1]-A[0]
        else :
            A=sorted(A)
            s=-99999
            for m in range(1,len(A)-1):
                s=max(s,A[m]-A[m-1],A[m+1]-A[m])
            return s

发表于 2019-03-19 22:29:17 回复(0)

Python

牛！

class MaxDivision:
def findMaxDivision(self, A, n):
A=sorted(A)
C=[]
for i in range(n):
if i < n-1:
C.append(abs(A[i]-A[i+1]))
return max(C)

编辑于 2019-03-05 15:23:08 回复(0)

Python

离疏

# -*- coding:utf-8 -*-
class MaxDivision:
    def findMaxDivision(self, A, n):
        A.sort()#应该用桶排序，此处偷懒
        ans=0
        for i in range(1,n):
            if A[i]-A[i-1]>ans:
                ans=A[i]-A[i-1]
        return ans

发表于 2018-08-03 15:08:11 回复(0)

Python

摇摇摆摆过大年

class MaxDivision:
    def findMaxDivision(self, A, n):
        sub = 0
        A.sort()
        for i in range(len(A)):
            if i == len(A)-1:
                break
            tem = A[i+1]-A[i]
            if tem > sub:
                sub = tem
        return sub

编辑于 2018-05-22 12:30:33 回复(0)

Python

华科平凡

python solution, easy to understand:


class MaxDivision:
    def findMaxDivision(self, A, n):
        res, A = 0, sorted(A)
        for i, v in enumerate(A):
            if i != n - 1:
                res = max(res, A[i + 1] - v)
        return res

发表于 2017-09-12 12:02:42 回复(3)

Python

我只是一个文弱小书生啊

class MaxDivision:
    def findMaxDivision( self,a, n):
        c=[]
        m=[]
        if len(a)<2 or len(a)>500:
            print ('无效')
        else:
            b=sorted(a)
            for i in range(len(b)):
                c.append(b[-len(b)+1+i])
            c[-1]=b[-1]
            for i in range(len(b)):
                m.append(c[i]-b[i])
        return max(m)

发表于 2017-04-20 10:19:53 回复(0)