Codeforces 1712C题解逻辑漏洞排查：数组排序最小操作数

给定一个由n个正整数a₁,a₂,…,aₙ组成的数组。

一次操作定义如下：选择任意整数x，将所有等于x的数组元素赋值为0。

求将数组排序为非递减顺序所需的最少操作次数。

输入格式 #

• 每组测试包含多组用例，第一行输入测试用例数t（1≤t≤10⁴）。
• 每个测试用例第一行输入整数n（1≤n≤10⁵）。
• 第二行输入n个正整数a₁,a₂,…,aₙ（1≤aᵢ≤n）。
• 保证所有测试用例的n之和不超过10⁵。

输出格式 #

每个测试用例输出一个整数，即所需的最少操作次数。

示例 #

输入示例 #

5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1

输出示例 #

1
2
4
3
0

说明 #

• 第一个测试用例中，选择x=3进行操作，得到数组[0,0,2]。
• 第二个测试用例中，先选x=1，再选x=3操作，得到数组[0,0,0,0]。

我的提交解法在隐藏测试用例中失败，请求指出逻辑漏洞或遗漏的边界情况。

我的逻辑思路 #

• 若数组非递减、长度为1或仅含一种元素，返回0；
• 若最后一个元素重复出现，返回数组中不同元素的数量；
• 若最后一个元素不重复，且倒数第二个元素小于最后一个元素，递归处理去掉最后一个元素的子数组；
• 若最后一个元素不重复，且倒数第二个元素≥最后一个元素，返回去掉最后一个元素的子数组中不同元素的数量。

我的代码 #

def distinct(arr):
    return len(set(arr))

def increase(arr):
    for i in range(len(arr)-1):
        if arr[i]>arr[i+1]:
            return False
    return True
    
def fun(arr,n):
    last_element=arr[-1]
    if (increase(arr)==True or len(arr)==1 or distinct(arr)==1):
        return 0
    elif (n-1 != (arr.index(last_element))):
        return distinct(arr)
    else:
        if arr[-2]<last_element:
            return fun(arr[:-1],n-1)
        else:
            return distinct(arr[:-1])

t=int(input())
while t>0:
    t=t-1
    n=int(input())
    arr=[int(x) for x in input().split()]
    print(fun(arr,n))

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