Python版求数组的最大连续区间

  1. 云栖社区>
  2. 博客>
  3. 正文

Python版求数组的最大连续区间

天外归云 2017-10-11 11:22:00 浏览1742
展开阅读全文

[本文出自天外归云的博客园]

题目:有一个数组,求他的最大(最长)连续区间(数字是连续的区间)。

我的解法,如下:

class Finder(object):
    '''
        判断两个相邻的数字是否连续,若连续:
            1.继续向后判断
            2.记录连续长度
        最后返回最大连续长度
    '''    
    def find_continuity(self,index,array,length=1):
        if index+1 < len(array):
            _curr = array[index]
            _next = array[index+1]
            if abs(_next-_curr) == 1:
                length += 1
                length = self.find_continuity(index+1,array,length)
        return length

    '''
        将每个数字开头的索引值及最大连续区间长度存入字典
        找出字典中最大的键值即最大连续区间
        根据最大连续区间的索引和长度返回对应的数组切片
    '''
    def find_longest(self,array):
        continuity = dict()
        for i in range(len(array)):
            length = self.find_continuity(i,array)
            continuity[i] = length
        longest = max(continuity.items(), key=lambda x: x[1])
        index,length = longest[0],longest[1]
        return array[index:index+length]

if __name__ == '__main__':
    array = [1,2,3,4,5,4,2,5,3,4,7,1,5,9,10,9,8,7,6,5,4,3,4,5,6,8]
    finder = Finder()
    longest_array = finder.find_longest(array)
    print(longest_array)

 

网友评论

登录后评论
0/500
评论
天外归云
+ 关注