请　[注册]　或　[登录]　 | 返回主站

量化交易吧 /  量化平台 帖子：3365825 新帖：0

MissingInteger-Find the smallest positive integer that does not occur in a given sequence.

我们棒棒哒发表于：5 月 10 日 06：40回复(1)

This is a demo task.

Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [?1, ?3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [?1,000,000..1,000,000].

QQ图片20190126022415.png
目前只能解决到O(N) or O(N * log(N))时间复杂度，望大神可以提出更好的算法解决

def solution(A):
    # write your code in Python 3.6
    n = len(A)
    if n <= 1:
        if 1 in A:
            return 2
        else:
            return 1
    else:
        if max(A) <= 0:
            return 1
        else:
            B = set(A)
            B = [stk for stk in B if stk > 0]
            B.sort()
            if min(B) >= 2:
                return 1
            else:
                a1 = min(B)
                C = list(range(a1,a1+len(B)))
                if B != C:
                    D = list(set(C)^set(B))
                    D.sort()
                    return D[0]
                else:
                    return B[-1] + 1

A = [1, 3, 6, 4, 1, 2]
print(solution(A))

5

       

全部回复

0/140

量化课程

    移动端课程