小编Bus*_*ust的帖子

我是第一次通过算法类的分析,并想知道是否有人可以协助下面的例子.我相信我已经解决了它的O(n)复杂性,但是想知道是否有更好的版本,我没有想到O(logn)？

设A = A [1] <= ... <= A [n + 1]是n个不同整数的排序数组,其中每个整数的范围为[1 ... n + 1].也就是说,A中缺少{1,...,n + 1}中的一个整数.描述一个efficeint算法来找到缺失的整数.分析算法的最坏情况复杂性(对数组A的访问次数).

我所拥有的解决方案相对简单,我相信在最坏的情况下会导致N的复杂性.也许我在想这个例子,但有更好的解决方案吗？

我的解决方案

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

这背后的逻辑是因为它被排序,第一个元素必须是1,第二个必须是2,依此类推,直到数组中的元素大于它应该是的元素,指示一个元素错过了,返回应该是的元素,我们有失踪的元素.

这是正确的逻辑吗？还有更好的方法吗？

感谢您的阅读并提前感谢您的帮助.

我有一个烧瓶项目,我开始学习flask-admin模块.

所需表的SqlAlchemy架构.

import datetime
import sqlalchemy
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import backref, relationship

Base = declarative_base()


class Workgroup(Base):
    __tablename__ = 'workgroups'
    id = sqlalchemy.Column(sqlalchemy.Integer,

                           primary_key=True,
                           autoincrement=True
                           )
    name = sqlalchemy.Column(sqlalchemy.String(16))
    shorthand = sqlalchemy.Column(sqlalchemy.String(4))

    def __unicode__(self):
        return self.name

class Drive(Base):
    """
    A drive in an edit station.
    """
    __tablename__ = 'drives'

    id = sqlalchemy.Column(sqlalchemy.Integer,
                           primary_key=True,
                           autoincrement=True
                           )
    name = sqlalchemy.Column(sqlalchemy.String(64))
    computer_id = sqlalchemy.Column(sqlalchemy.Integer,
                                    sqlalchemy.ForeignKey(Computer.id)
                                    )
    computer = relationship('Computer', backref='drives')
    is_active = sqlalchemy.Column(sqlalchemy.Boolean)
    free_space = sqlalchemy.Column(sqlalchemy.BigInteger)
    used_space = sqlalchemy.Column(sqlalchemy.BigInteger)
    total_space …