使用递归函数统计元素出现次数时遇NoneType错误求助

问题背景 #

我编写了一段Python代码用于统计有序列表中元素的出现次数，逻辑如下：

• count_occur()调用first_occur()获取元素首次出现的索引；
• 调用last_occur()获取元素末次出现的索引；
• 通过首尾索引差值计算出现次数。

原代码 #

# calculates the first occurrence of the element
def first_occur(lists, k, low, high): 
    mid = (low+high)//2
    if low > high:
        return -1

    # condition to calculate the first occurrence
    if lists[mid]==k:
        if mid==0 or lists[mid-1]!=lists[mid]:
            return mid
        else:
            return first_occur(lists,k,low,mid-1)
    elif lists[mid]<k:
        first_occur(lists,k,mid+1,high)
    else:
        first_occur(lists,k,low,mid-1)

     
# calculates the last occurrence of the element
def last_occur(lists,k,low,high):
    mid = (low + high)//2
    if low > high:
        return -1

    #condition to check the last occurrence
    if lists[mid] == k:
        if mid == len(lists)-1 or lists[mid+1] != lists[mid]:
            return mid
        else:
            return first_occur(lists,k,mid+1,high)
    elif lists[mid]<k:
        first_occur(lists,k,mid+1,high)
    else:
        first_occur(lists,k,low,mid-1)
        
        
# called via the input
def count_occur(lists,k):
    l = len(lists)
    fo = first_occur(lists,k,0,l)
    print(fo)
    lo = last_occur(lists,k,0,l)
    print(lo)
    
    if fo == -1:
        print('Not found')
    else:
        # checks for the number of occurrences
        print("Found",(fo-lo+1),"times.")
        
        
# getting input via the user of the list.
a = list(map(int, input().split()))
print(a)

k = int(input("Enter the number, the occurences of which to be found."))

count_occur(a, k)

运行错误输出 #

12 34 56
[12, 34, 56]
Enter the number, the occurrences of which to be found.12
None
None
Traceback (most recent call last):
  File "/Users/somilsharma/Desktop/DSA/14.py", line 79, in <module>
    count_occur(a,k)
  File "/Users/somilsharma/Desktop/DSA/14.py", line 70, in count_occur
    print("Found",(fo-lo+1),"times.")
                   ~~^~~
TypeError: unsupported operand type(s) for -: 'NoneType' and 'NoneType'

错误原因分析 #

1. 递归调用未返回值：first_occur和last_occur中，当lists[mid] < k或lists[mid] > k时，仅调用递归函数但未用return返回结果，导致函数默认返回None。
2. last_occur函数内递归调用错误：在last_occur的递归分支中，错误调用了first_occur，应调用自身last_occur。
3. 索引范围越界：调用first_occur和last_occur时，传入的high参数为列表长度l，但列表最大合法索引是len(lists)-1，会导致递归中访问超出列表范围的索引。
4. 出现次数计算逻辑错误：正确次数应为末次索引 - 首次索引 + 1，原代码写反为fo-lo+1，会得到负数结果。

修正后的代码 #

# 计算元素首次出现的索引
def first_occur(lists, k, low, high): 
    mid = (low + high) // 2
    if low > high:
        return -1

    if lists[mid] == k:
        if mid == 0 or lists[mid-1] != lists[mid]:
            return mid
        else:
            return first_occur(lists, k, low, mid-1)
    elif lists[mid] < k:
        return first_occur(lists, k, mid+1, high)
    else:
        return first_occur(lists, k, low, mid-1)

     
# 计算元素末次出现的索引
def last_occur(lists, k, low, high):
    mid = (low + high) // 2
    if low > high:
        return -1

    if lists[mid] == k:
        if mid == len(lists)-1 or lists[mid+1] != lists[mid]:
            return mid
        else:
            return last_occur(lists, k, mid+1, high)
    elif lists[mid] < k:
        return last_occur(lists, k, mid+1, high)
    else:
        return last_occur(lists, k, low, mid-1)
        
        
# 统计出现次数的入口函数
def count_occur(lists, k):
    l = len(lists)
    fo = first_occur(lists, k, 0, l-1)
    lo = last_occur(lists, k, 0, l-1)
    
    if fo == -1:
        print('Not found')
    else:
        print(f"Found {lo - fo + 1} times.")
        
        
# 用户输入部分
a = list(map(int, input().split()))
print(a)

k = int(input("Enter the number, the occurrences of which to be found."))

count_occur(a, k)

测试验证 #

输入测试用例：

12 34 56
[12, 34, 56]
Enter the number, the occurrences of which to be found.12

输出结果：

Found 1 times.

若输入含重复元素的列表12 12 34 56，查询12会输出Found 2 times.，符合预期。

内容的提问来源于stack exchange，提问作者SomilSharma