时间戳

首页 > 解决方案 > 查找列表中的正数个数

python - 查找列表中的正数个数

问题描述

我正在尝试使用 python 在列表中查找正数的数量，我希望代码在 O(log(n)) 中运行，如果有负数，列表的类型为正负数，它们将位于右侧列表和所有积极因素都在左侧。例如，如果输入是：

lst=[2,6,0,1,-3,-19]

输出是

4

我尝试了一些方法，但没有得到我想要的结果，这是我到现在为止得到的最后一种形式：

def pos_neg(lst):
    if int(len(lst)) is 0 or (int(len(lst)) is 1 and lst[0] <0):
        return 0
    elif len(lst) is 1 and lst[0] >=0:
        return 1
    leng = (int(len(lst))) // 2
    counter = 0
    index = 0
    while(leng != 0):
        if lst[leng]  >=0 and lst[leng+1] <0:
            index = leng
            break
        if lst[leng] >=0 and lst[leng + 1] >=0:
            if int(len(lst)) < leng + int(len(lst)):
                return 0
            else:
                leng = (leng + int(len(lst))) // 2
        if lst[leng] <0 and lst[leng + 1] <0:
        leng = leng // 2
    return index

标签： pythonlist

解决方案

您可以使用递归。每次列表减半，所以复杂度为 O(logn)

def find_pos(start, end, l, count):
    if(start > end):
        return count
    middle = start + (end-start)//2
    if(l[middle] >= 0): # that means all left side is positive
        count += (middle-start) + 1
        return find_pos(middle+1, end, l, count)
    else: # that means I am in wrong region
        return find_pos(start, middle-1, l, count)

lst=[2,6,0,1,-3,-19]
find_pos(0, len(lst)-1, lst, 0)

>>> 4

更新：如果你想要一个只传递 lst 的函数

def find_positives(l):
    return find_pos(0, len(l)-1, l, 0)
find_positives(lst)

推荐阅读