主页 / coding / 问题 / 78968406
Accepted
Peter Wu
Asked: 2024-09-10 15:43:01 +0800 CST

最小化 (s[i]-s[j]+d)/(ij) 的算法

  • 772

该问题基于 leetcode 竞赛问题 ( https://doocs.github.io/leetcode/en/lc/3281/ )。可以将其简化为以下问题：设s为已排序数组，d为正整数，最小化 ( s [i]- s [j]+ d )/(ij)。其中 i>j。

大多数答案都是基于二分搜索来限制最优解，其时间复杂度取决于 max( s )-min( s )。那么，是否有可能构建一个相对于s大小线性/次二次的算法？

algorithm

1 个回答

  1. Best Answer

    您可以在 O(n log n) 时间内完成此操作。

    s[i]首先，请注意，如果我们要沿着高点绘制低点图s[i]+d，那么我们的任务就是找到从低点到其右侧高点的斜率最小的线。

    当我们迭代高点时，我们可以确定其左侧的哪个低点与最小斜率相连，然后记住最佳的那个。

    我们可以在 O(log n) 时间内找到最佳连接点，因为它保证位于左侧低点的上凸包上。当我们遍历高点时，我们可以使用单调链算法同时构建其左侧低点的上凸包。这每个点需要摊销常数时间。

    给定左侧点的上凸包，我们可以使用二分查找来找到最佳连接点，因为凸包各段的斜率单调递减。对于最佳连接点左侧的所有段，当前最高点将位于其线的下方或线上，而对于最佳连接点右侧的所有段，当前最高点将位于其线的上方或线上。

    在此处输入图片描述

    以下是 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

相关问题