在O(logn)时间复杂度内解决代码的困难

Question

在O(logn)时间复杂度内解决代码的困难

7

我写了一个函数，它的输入是一个按照从小到大顺序排列的唯一整数列表。我应该在列表中找到与索引值相匹配的索引。例如，如果L[2]==2，则输出为true。因此，在O(logn)的复杂度下完成了第一部分后，现在我想找出在给定列表中有多少个索引像这样行为的索引，其复杂度也为O(logn)。我上传了我的第一个代码来完成第一部分，以及我需要帮助的第二个代码：

def steady_state(L):

    lower= 0
    upper= len(L) -1
    while lower<=upper:
        middle_i= (upper+ lower)//2
        if L[middle_i]== middle_i:
            return middle_i
        elif L[middle_i]>middle_i:
            upper= middle_i-1
        else:
            lower= middle_i +1
    return None


def cnt_steady_states(L):
    lower= 0
    upper= len(L) -1
    a=b=steady_state(L)
    if steady_state(L)== None:
        return 0
    else:
        cnt=1
        while True:

            if L[upper] == upper and a<=upper:
                cnt+= upper-a
                upper= a
            if L[lower]== lower and b>=lower:
                cnt+= b- lower
                lower = b

- user2751595

这些整数可以是负数吗？ - hankd

3个回答

1

假设负整数也可以：

我认为关键在于，如果你得到一个比你的索引小的值，那么你知道所有左侧的索引也不匹配它们的值（因为整数是严格递增的）。同样地，一旦你得到一个值大于索引的索引，右侧的所有内容都是不正确的（同样的原因）。然后你可以像第一种情况一样使用分治算法。大致如下：

check middle index:
    if equal:
        count = count + 1 
        check both halves, minus this index
    elif value > index:
        check left side (lower to index)
    elif index > value:
        check right side (index to upper)

在最坏的情况下（每个索引都匹配值），我们仍然需要检查每个索引。

如果整数是非负的，那么你知道更多。现在你还知道，如果一个索引与该值匹配，所有左侧的索引也必须匹配该值（为什么？）。因此，你可以得到：

check middle index:
    if equal:
        count = count + indices to the left (index-lower)
        check the right side (index to upper)
    elif value > index:
        check left side (lower to index)
    elif index > value:
        ##Can't happen in this case

现在，我们的最坏情况有了显著改善。与其找到一个匹配的索引却没有获得任何新信息，当我们找到一个匹配的索引时，我们会获得大量信息，并且现在知道一半的索引是匹配的。

- hankd

1

如果“所有数字都是整数且仅出现一次”，那么您可以简单地进行二分搜索，找到第一对数字，其中L[i]==i && L[i+1]!=i+1。

为了允许负整数，请检查L[0]<0，如果是这样，请在1..N之间搜索：
i>0 && L[i]==i && L[i-1]!=i-1。然后在i和N之间执行先前的搜索。

- AShelly

如果整数可以为负数，您仍然不知道哪些小于i的索引与它们的值匹配。 - hankd

另外，在第二部分中，你是不是想说 L[i+1] != i+1？因为 L[i] == i 总是意味着 L[i+1] != i。 - hankd

i+1 很好的捕捉。如果整数可以为负数，则测试将被反转。编辑中。 - AShelly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alfe · Accepted Answer

目前根据你所给出的限制，这是不可能实现的。在理论上，你能够达到的最佳复杂度为O(n)。

O()假设最坏情况（这只是一个定义，你可以忽略这部分）。在最坏情况下，你将始终需要检查每个项目是否等于其索引。

如果你有更多限制（例如数字都是整数且没有重复出现，即没有两个连续的数字相等），情况就会改变。也许这就是你的情况？

编辑：

在听说实际上我的假定限制适用时（即仅出现一次的整数），我现在提出以下方法：你可以安全地假设你只能拥有一个连续范围，在这个范围内所有匹配的条目都位于其中。也就是说，你只需要找到一个下限和上限。所需结果将是该范围的大小。

每个边界都可以使用二分搜索安全地找到，其中每个都具有O(logn)的复杂度。

def binsearch(field, lower=True, a=0, b=None):
  if b is None:
    b = len(field)
  while a + 1 < b:
    c = (a + b) / 2
    if lower:
      if field[c] < c:
        a = c
      else:
        b = c
    else:  # search for upper bound
      if field[c] > c:
        b = c
      else:
        a = c
  return b if lower else a

def indexMatchCount(field):
  upper = binsearch(field, lower=False)
  lower = binsearch(field, b=upper+1)
  return upper - lower + 1

我用这个来进行测试:

field = list({ random.randint(-10, 30) for i in range(30) })
field.sort()
upper = binsearch(field, lower=False)
lower = binsearch(field, b=upper+1)
for i, f in enumerate(field):
  print lower <= i <= upper, i == f, i, f