我如何编写这个算法 returns 列表中 x 和 y 之间的计数？

Question

我遇到了这个算法问题，需要找到一种方法来 return 列表 S 和另一个列表 L 中的一些变量 x 和一些变量 y 之间的计数，包括运行在O(1) 时间：

I've issued a challenge against Jack. He will submit a list of his favorite years (from 0 to 2020). If Jack really likes a year, he may list it multiple times. Since Jack comes up with this list on the fly, it is in no particular order. Specifically, the list is not sorted, nor do years that appear in the list multiple times appear next to each other in the list.

I will also submit such a list of years.

I then will ask Jack to pick a random year between 0 and 2020. Suppose Jack picks the year x.

At the same time, I will also then pick a random year between 0 and 2020. Suppose I pick the year y. Without loss of generality, suppose that x ≤ y.

Once x and y are picked, Jack and I get a very short amount of time (perhaps 5 seconds) to decide if we want to re-do the process of selecting x and y.

If no one asks for a re-do, then we count the number of entries in Jack's list that are between x and y inclusively and the number of entries in my list that are between x and y inclusively.

从技术上讲，情况是这样的。给定 m 和 n 个整数的列表 S 和 L，分别在[0, k]范围内，代表Jack和 I. 你可以在 O(m+n+k) 时间内预处理 S 和 L。然后你必须给出一个算法在 O(1) 时间内运行——这样我就可以决定是否需要重做——解决了以下问题：

输入： 两个整数，x 作为 [0,k] 的成员，y 作为 [0,k]

的成员

输出： S 中 [x, y] 范围内的条目数，以及 L 中 [x, y] 内的条目数。

例如，假设 S = {3, 1, 9, 2, 2, 3, 4}。给定 x = 2 和 y = 3，returned 计数将是 4.

我更喜欢伪代码；它帮助我更容易理解问题。

Answer 1

实施 user3386109 的方法处理 x = 0 的边缘情况。

user3386109 : 做一个直方图，然后计算直方图中每个条目的累加和。假设S={3,1,9,2,2,3,4}，k为9，直方图为H={0,1,2,2,1,0,0,0,0,1}。累加后，H={0,1,3,5,6,6,6,6,6,7}。给定 x=2 和 y=3，计数为 H[y] - H[x-1] = H[3] - H[1] = 5 - 1 = 4。当然，x=0 是极端情况必须处理。

# INPUT

S = [3, 1, 9, 2, 2, 3, 4]
L = [2, 9, 4, 6, 8, 5, 3]
k = 9

x = 2
y = 3

# Histogram for S
S_hist = [0]*(k+1)

for element in S:
    S_hist[element] = S_hist[element] + 1

# Storing prefix sum in S_hist 
sum = S_hist[0]
for index in range(1,k+1):
    sum = sum + S_hist[index]
    S_hist[index] = sum


# Similar approach for L

# Histogram for L
L_hist = [0] * (k+1)

for element in L:
    L_hist[element] = L_hist[element] + 1
    
# Stroing prefix sum in L_hist
sum = L_hist[0]
for index in range(1,k+1):
    sum = sum + L_hist[index]
    L_hist[index] = sum
    
# Finding number of elements between x and y (inclusive) in S
print("number of elements between x and y (inclusive) in S:")
if(x == 0):
    print(S_hist[y])
else:
    print(S_hist[y] - S_hist[x-1])
    
# Finding number of elements between x and y (inclusive) in S
print("number of elements between x and y (inclusive) in L:")
if(x == 0):
    print(L_hist[y])
else:
    print(L_hist[y] - L_hist[x-1])

我如何编写这个算法 returns 列表中 x 和 y 之间的计数？

How can I write this algorithm that returns the count between x and y in a list?

list

algorithm

dictionary

pseudocode