Início / coding / Perguntas / 78968406
Accepted
Peter Wu
Asked: 2024-09-10 15:43:01 +0800 CST

Algoritmo para minimizar (s[i]-s[j]+d)/(ij)

  • 772

O problema é baseado em um problema de concurso leetcode ( https://doocs.github.io/leetcode/en/lc/3281/ ). Pode-se reduzi-lo ao seguinte problema: seja s um array ordenado e d um inteiro positivo, minimize ( s [i]- s [j]+ d )/(ij). Em que i>j.

A maioria das respostas foi baseada em busca binária para limitar uma solução ótima, para a qual a complexidade de tempo é dependente de max( s )-min( s ). Então é possível construir um algoritmo que seja linear/subquadrático em relação ao tamanho de s ?

algorithm

1 respostas

  1. Best Answer

    Você pode fazer isso em tempo O(n log n).

    Primeiro, observe que se representássemos graficamente os pontos baixos s[i]junto com os pontos altos s[i]+d, nossa tarefa seria encontrar a linha com a menor inclinação possível de um ponto baixo para um ponto alto à sua direita.

    À medida que iteramos pelos pontos altos, podemos determinar qual dos pontos baixos à esquerda se conecta com a menor inclinação e, então, lembrar qual é o melhor.

    Podemos encontrar o melhor ponto de conexão em tempo O(log n), porque é garantido que ele esteja no casco convexo superior dos pontos baixos à esquerda. Conforme iteramos pelos pontos altos, podemos usar o algoritmo de cadeia monótona para construir simultaneamente o casco convexo superior dos pontos baixos à sua esquerda. Isso leva tempo constante amortizado por ponto.

    Dado o casco convexo superior de pontos à esquerda, podemos usar uma busca binária para encontrar o melhor ponto de conexão, porque a inclinação dos segmentos do casco convexo diminui monotonicamente. Para todos os segmentos à esquerda do melhor ponto de conexão, o ponto alto atual estará abaixo ou em sua linha, e para todos os segmentos à direita do melhor ponto de conexão, o ponto alto atual estará acima ou em sua linha.

    insira a descrição da imagem aqui

    Aqui está uma implementação em python:

    
# is n1/d1 < n2/d2 ?
def fracLessThan(n1,d1,n2,d2):
    return n1*d2 < n2*d1

def minSlope(s,d):
    if len(s) < 2:
        return None
    s = sorted(s)
    # parallel arrays to keep track of the upper convex hull of previous points
    hullx = [0,1]
    hully = [s[0],s[1]]
    # keep track of the best slope as a fraction
    bestSlope = (s[1]+d-s[0], 1)
    for x in range(2, len(s)):
        y = s[x]+d
        # binary search find the best connecting slope
        l = 0
        h = len(hullx)-1
        while(l<h):
            mid = l + (h-l)//2
            # is (x,y) below the segment after mid?
            if fracLessThan(y-hully[mid], x-hullx[mid], hully[mid+1]-hully[mid], hullx[mid+1]-hullx[mid]):
                # yes.  mid is too low
                l = mid+1
            else:
                # no. mid is high enough
                h = mid
        # best connecting point slope
        num = y - hully[l]
        den = x - hullx[l]
        if fracLessThan(num, den, bestSlope[0], bestSlope[1]):
            bestSlope = (num, den)
        
        # update the convex hull
        y = s[x]
        while len(hullx) > 1:
            lastn = hully[-1] - hully[-2]
            lastd = hullx[-1] - hullx[-2]
            testn = y - hully[-2]
            testd = x - hullx[-2]
            if (fracLessThan(testn, testd, lastn, lastd)):
                break
            hullx.pop()
            hully.pop()
        hullx.append(x)
        hully.append(y)

    return bestSlope

ans = minSlope([0,5,6,9,10,12],4)
# prints 11/4
print("min slope is {0}/{1}".format(ans[0], ans[1]))
    • 2

relate perguntas