python A[i]和B[i]之间差值的最小绝对值(数组A严格递增，数组B严格递减)

ubof19bj 于 2023-01-29 发布在 Python

关注(0)|答案(1)|浏览(159)

给定两个长度相同的序列A和B：一个是严格递增的，另一个是严格递减的，需要找到一个索引i，使得A[i]和B[i]之差的绝对值最小，如果有多个这样的索引，答案就是其中最小的一个，输入序列是标准的Python数组，保证它们的长度相同，效率要求：渐近复杂度：不超过输入序列长度的对数的幂。我已经使用黄金分割法实现了索引查找，但是我对浮点运算的使用感到困惑。是否有可能以某种方式改进这个算法，以便不使用它，或者你能想出一个更简洁的解决方案吗？

import random
import math
def peak(A,B):
    def f(x):
        return abs(A[x]-B[x])
    phi_inv = 1 / ((math.sqrt(5) + 1) / 2)
    def cal_x1(left,right):
        return right - (round((right-left) * phi_inv))
    def cal_x2(left,right):
        return left + (round((right-left) * phi_inv))
    left, right = 0, len(A)-1
    x1, x2 = cal_x1(left, right), cal_x2(left,right)
    while x1 < x2:
        if f(x1) > f(x2):
            left = x1
            x1 = x2
            x2 = cal_x1(x1,right)
        else:
            right = x2
            x2 = x1
            x1 = cal_x2(left,x2)
    if x1 > 1 and f(x1-2) <= f(x1-1): return x1-2
    if x1+2 < len(A) and f(x1+2) < f(x1+1): return x1+2
    if x1 > 0 and f(x1-1) <= f(x1): return x1-1
    if x1+1 < len(A) and f(x1+1) < f(x1): return x1+1
    return x1

#value check
def make_arr(inv):
    x = set()
    while len(x) != 1000:
        x.add(random.randint(-10000,10000))
    x = sorted(list(x),reverse = inv)
    return x

x = make_arr(0)
y = make_arr(1)
needle = 1000000
c = 0
for i in range(1000):
    if abs(x[i]-y[i]) < needle:
        c = i
        needle = abs(x[i]-y[i])
print(c)
print(peak(x,y))

python

来源：https://stackoverflow.com/questions/75267443/minimal-absolute-value-of-the-difference-between-ai-and-bi-array-a-is-stric

1条答案

按热度按时间

6tdlim6h1#

方法

发帖者询问可供选择的、更简单的解决方案。
这个问题是Leetcode Problem 852的一个变种，它的目标是在一个mountain数组中找到一个peak索引，我们通过计算abolute差值的负值来转换为peak，而不是min，我们的方法是将这个Python solution问题修改为Leetcode问题。

代码

def binary_search(x, y):
    ''' Mod of https://walkccc.me/LeetCode/problems/0852/ to use function'''
    def f(m):
        ' Absoute value of difference at index m of two arrays '
        return -abs(x[m] - y[m])    # Make negative so we are looking for a peak
            
    # peak using binary search
    l = 0
    r = len(arr) - 1

    while l < r:
      m = (l + r) // 2
      if f(m) < f(m + 1):    # check if increasing
        l = m + 1
      else:
        r = m                 # was decreasing

    return l

测试

def linear_search(A, B):
    ' Linear Search Method '
    values = [abs(ai-bi) for ai, bi in zip(A, B)]
    return values.index(min(values))     # linear search
    
def make_arr(inv):
    random.seed(10)    # added so we can repeat with the same data
    x = set()
    while len(x) != 1000:
        x.add(random.randint(-10000,10000))
    x = sorted(list(x),reverse = inv)
    return x

# Create data
x = make_arr(0)
y = make_arr(1)

# Run search methods
print(f'Linear Search Solution {linear_search(x, y)}')
print(f'Golden Section Search Solution {peak(x, y)}') # posted code
print(f'Binary Search Solution {binary_search(x, y)}')

产出

Linear Search Solution 499
Golden Section Search Solution 499
Binary Search Solution 499

赞(0）回复(0）举报 2023-01-29

我来回答

python A[i]和B[i]之间差值的最小绝对值(数组A严格递增，数组B严格递减)

1条答案

相关问题

热门标签

最新问答