设计用于在列表中查找 3 个不同元素的 O(log n) 算法

Question

问题是：

Design an O(log n) algorithm whose input is a sorted list A. The algorithm should return true if A contains at least 3 distinct elements. Otherwise, the algorithm should return false.

因为它必须是 O(log n)，我尝试使用二进制搜索，这是我写的代码：

def hasThreeDistinctElements(A):
    if len(A) < 3:
        return False
    minInd = 0
    maxInd = len(A)-1
    midInd = (maxInd+minInd)//2
    count = 1
    while minInd < maxInd: 
        if A[minInd] == A[midInd]:
            minInd = midInd
            if A[maxInd] == A[midInd]:
                maxInd = midInd
            else:
                count += 1
                maxInd -= 1
        else:
            count += 1
            minInd += 1
        midInd = (maxInd+minInd)//2
  
    return count >= 3

有更好的方法吗？

谢谢

Answer 1

是的，有更好的方法。

由于列表已排序，您可以使用二分查找并稍作自定义修改，如下所示：

list = [1, 1, 1, 2, 2]

uniqueElementSet = set([])

def binary_search(minIndex, maxIndex, n):
    
    if(len(uniqueElementSet)>=3):
        return
        
    #Checking the bounds for index:
    if(minIndex<0 or minIndex>=n or maxIndex<0 or maxIndex>=n):
        return
    
    if(minIndex > maxIndex):
        return
    
    if(minIndex == maxIndex):
        uniqueElementSet.add(list[minIndex])    
        return
    
    if(list[minIndex] == list[maxIndex]):
        uniqueElementSet.add(list[minIndex])    
        return
    
    uniqueElementSet.add(list[minIndex])
    uniqueElementSet.add(list[maxIndex])
    
    midIndex = (minIndex + maxIndex)//2
    
    binary_search(minIndex+1, midIndex, n)
    
    binary_search(midIndex+1, maxIndex-1, n)
    
    return

binary_search(0, len(list)-1, len(list))

print(True if len(uniqueElementSet)>=3 else False)

因为，我们在递归的每次迭代中将数组分成两部分，它最多需要 log(n) 步来检查它是否包含 3 个唯一元素。

时间复杂度 = O(log(n)).

Answer 2

为了真正成为 O(logN)，对边界索引 minInd,maxInd 的更新应该永远是

maxInd = midInd [- 1]
minInd = midInd [+ 1]

搜索减半 space。因为有通过你的循环体的路径只做

minInd += 1
maxInd -= 1

分别，我不确定您不能创建您的函数是线性的数据。下面简单一点，保证O(logN)

def x(A):
    if len(A) < 3:
        return False
    minInd, maxInd = 0, len(A)-1
    mn, mx = A[minInd], A[maxInd]

    while minInd < maxInd:
        midInd = (minInd + maxInd) // 2
        if mn != A[midInd] != mx:
            return True
        if A[midInd] == mn:
            minInd = midInd + 1  # minInd == midInd might occur 
        else:
            maxInd = midInd  # while maxInd != midInd is safe

    return False

顺便说一句，如果你会使用标准库，那就很简单了：

from bisect import bisect_right

def x(A):
    return A and (i := bisect_right(A, A[0])) < len(A) and A[i] < A[-1]

Answer 3

from bisect import bisect

def hasThreeDistinctElements(A):
    return A[:1] < A[-1:] > [A[bisect(A, A[0])]]

第一次安全比较^(*) 检查是否有两个不同的值。如果是，我们检查第一个大于 A[0] 的值是否也小于 A[-1].

(*)：如果 A 为空，则不会崩溃。

或没有 bisect，二进制搜索 A[1:-1] 中的第三个值。不变量是如果有的话，一定在A[lo : hi+1]:

def hasThreeDistinctElements(A):
    lo, hi = 1, len(A) - 2
    while lo <= hi:
        mid = (lo + hi) // 2
        if A[mid] == A[0]:
            lo = mid + 1
        elif A[mid] == A[-1]:
            hi = mid - 1
        else:
            return True
    return False

设计用于在列表中查找 3 个不同元素的 O(log n) 算法

Design O(log n) algorithm for finding 3 distinct elements in a list

python

algorithm

big-o

time-complexity