时间戳

首页 > 解决方案 > 查找整数是否存在于范围列表中

algorithm - 查找整数是否存在于范围列表中

问题描述

给定一个包含 1,000,000 个唯一整数的数组 N，范围从 0 到 1,999,999。过滤掉 M 内任何范围内不存在的整数的最快方法是什么 - 其中 M 是 10 个随机范围的固定组，每个范围的整数范围为 0 到 1,999,999？

数字较小的短样本：

给定这组 N 个唯一整数：[1,5,7,8,20,22,30] 和这组 M 个范围：[(1,6) , (19,21), (23,50)]

找出在 M 的任何范围内存在的 N 值（包括边界）

解决方案：[1,5,20,30]

Java 是首选（运行时间/复杂性测试），但任何其他语言都可以

标签： algorithmsortingdata-sciencemathematical-optimizationdata-scrubbing

解决方案

使用python3。希望这会有所帮助

import numpy as np
ranges = [(1,6) , (19,21), (23,50)]
nums = [1,5,7,8,20,22,30]

max = ranges[-1][1]
ind_array = np.zeros(max)

for r in ranges:
  ind_array[r[0]-1:r[1]] = 1

lst = []
for n in nums:
  if ind_array[n-1] == 1:
    lst.append(n)

print(lst)

推荐阅读