设计O（logn）算法在一个列表中查找3个不同的元素

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（logn），我尝试使用二进制搜索，下面是我编写的代码：

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

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

Answer 2

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

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

搜索空间的一半。因为通过循环体的路径只有

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

是的，有更好的方法

在对列表进行排序后，您可以使用二进制搜索，只需稍作自定义修改，如下所示：

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)

当我们在递归的每次迭代中将数组分成2部分时，它将需要最多log（n）个步骤来检查它是否包含3个唯一的元素

时间复杂度=O（log（n））。