在有序列表中获取唯一相邻整数的 Pythonic 方法

Question

给定一个有序整数列表，return 小于 N 的最大整数和大于 N 的最小整数。如果有 none 个，就打印“X”。

Answer 1

给你！您的代码特别慢，而且数字差异很大。例如[0, 752,15000,670000,37452846,3826848827,10000000000] 与数字参数 40000000。我想如果你想要 reeeally huuuuge 列表，你也可以做二进制搜索类型的事情，但这些非常烦人。

def solution(list_, n):
    l = list(filter(lambda p: p != n, sorted(list_[:])))
    for i, x in enumerate(l):
        if x > n: break
    else: return [l[-1], "X"]
    return [l[i-1], l[i]] if i else ["X", l[i]]

Answer 2

希望您理解这一点

li = [2, 4, 6, 8]
n = 9

#l for largest int lesser than n, s for smallest int greater than n
l = 'X'
s = 'X'

#insert n to list and ordered it
li.append(n)
li.sort()

#get the index of n in the list
index_n = li.index(n)

#if the n is not the smallest value in list, we assign the value before n to l
if index_n > 0:
    l = str(li[index_n - 1])

#if the n is not the greatest value in list, we assign the value after n to s
if index_n < len(li)-1:
    s = str(li[index_n + 1])
    
print(l,s)

Answer 3

不必想太多；这在我的系统（一些现代笔记本电脑 i7）上出奇地快并且感觉非常 Pythonic

# /usr/bin/env python3

# create ordered list of values
# NOTE that this need not be included in the algorithm time
l = list(range(0, 25000*3, 3))
print(len(l))

# pick some large n outside of the list l
n = 1000000

# try to find the min and max before and after N
try:
    a = max(x for x in l if x < n)
except ValueError:
    a = 'X'

try:
    b = min(x for x in l if x > n)
except ValueError:
    b = 'X'

print(a,b)

% time python3 so64964821.py
25000
74997 X
python3 so64964821.py  0.02s user 0.01s system 87% cpu 0.036 total

Answer 4

据我所知，这是最快的解决方案。

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    lm = -1
    while low <= high:
        lm = mid
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
        if lm == mid:break
    return mid

def find_next_bigger(arr,n,i):
    while i < len(arr):
          if arr[i] > n:
              return arr[i]
          i += 1
    return arr[i] if i < len(arr) else "X"

def find_next_smaller(arr, n,i):
        while i >= 0:
            if arr[i] < n:
                return arr[i]
            i -= 1
        return arr[i] if i > 0 else "X"

def solution(arr, n):
    if n > arr[-1]:
        return arr[-1], "X"
    if arr[0] > n:
          return "X", arr[0]
    i = binary_search(arr, n)
    bigger = find_next_bigger(arr, n, i)
    smaller = find_next_smaller(arr,n,i)
    return smaller, bigger

Answer 5

使用标准库使事情变得简单——而且库方法通常经过优化且速度很快。 bisect模块（link）有你想要的：

from bisect import bisect_left
sorted_list = list(range(0, 50000, 2))
insertion_point = bisect_left(sorted_list, 15001)
below = sorted_list[insertion_point - 1]
above = sorted_list[insertion_point]
print(below, above)

$ python bis.py
15000 15002

bisect_left 使用 binary search 查找“插入点”——您将在列表中插入此新数字以维护当前排序顺序的索引。这正是您找到号码邻居所需要的。

这是一个开始。如果您的数字超出排序列表中的整数范围，则需要更多逻辑来打印 'X'。

可以找到 bisect_left 的源代码 here，值得一看。非常简单。

在有序列表中获取唯一相邻整数的 Pythonic 方法

Pythonic Way to Get Unique Neighboring Integers in an Ordered List

python

search

integer

loops