搜狐面试题 - Justin的博客

人生参加的第一次招聘，遇到一道不错的好题分享给大家：
求数组[6,3,1,2,5]中最长的数值连续子序列的长度
本人答案如下：

import numpy as np


def mergeSort(lyst):
    copyBuffer = np.zeros(len(lyst), dtype=int)
    mergeSortHelper(lyst, copyBuffer, 0, len(lyst) - 1)


def mergeSortHelper(lyst, copyBuffer, low, high):
    if low < high:
        middle = (low + high) // 2
        mergeSortHelper(lyst, copyBuffer, low, middle)
        mergeSortHelper(lyst, copyBuffer, middle + 1, high)
        merge(lyst, copyBuffer, low, middle, high)


def merge(lyst, copyBuffer, low, middle, high):
    i1 = low
    i2 = middle + 1

    for i in range(low, high + 1):
        if i1 > middle:
            copyBuffer[i] = lyst[i2]
            i2 += 1
        elif i2 > high:
            copyBuffer[i] = lyst[i1]
            i1 += 1
        elif lyst[i1] < lyst[i2]:
            copyBuffer[i] = lyst[i1]
            i1 += 1
        else:
            copyBuffer[i] = lyst[i2]
            i2 += 1
    for i in range(low, high + 1):
        lyst[i] = copyBuffer[i]


def search(lyst):
    mergeSort(lyst)
    i = 0
    start = i
    sum = 0
    lengest = 0
    while i < len(lyst)-1:
        if lyst[i + 1] == lyst[i] + 1:
            i += 1
        else:
            sum = i - start + 1
            if sum > lengest:
                lengest = sum
            i += 1
            start = i
    sum = i - start + 1
    if sum > lengest:
        lengest = sum
    return lengest