这是我遇到的一个有趣的编程难题。给定一个正整数数组和一个数字 K。我们需要从数组中找到对 (a,b) 使得a % b = K.
我对此有一个简单的O(n^2)解决方案，我们可以检查所有对，例如 a%b=k。有效但效率低下。我们当然可以做得比这更好，不是吗？任何有效的算法相同？哦，这不是家庭作业。
问问题
5028 次
3 回答
6
对您的数组和二进制搜索进行排序或保留一个哈希表，其中包含数组中每个值的计数。
对于一个数x，我们可以找到最大的y如。对此进行二进制搜索或在您的哈希中查找它并相应地增加您的计数。x mod y = Ky = x - Ky
现在，这不一定是唯一可行的值。例如，8 mod 6 = 8 mod 3 = 2。我们有：
x mod y = K => x = q*y + K =>
=> x = q(x - K) + K =>
=> x = 1(x - K) + K =>
=> x = 2(x - K)/2 + K =>
=> ...
这意味着您还必须测试所有除数y。您可以在 中找到除数，如果使用二分搜索和哈希表（尤其是在您的数字不是很大的情况下，建议使用），您可以O(sqrt y)得到总的复杂性。O(n log n sqrt(max_value))O(n sqrt(max_value))
于 2012-10-04T18:53:04.233 回答
0
将问题视为有两个单独的数组作为输入：一个用于 a 数字，a % b = K 和一个用于 b 数字。我将假设一切都> = 0。
首先，您可以丢弃任何 b <= K。
现在将 b 中的每个数字视为生成一个序列 K、K + b、K + 2b、K + 3b...您可以使用一对数字 (pos, b) 记录这一点，其中 pos 每次递增 b阶段。从 pos = 0 开始。
将这些序列保存在优先级队列中，这样您就可以在任何给定时间找到最小的 pos 值。对数字数组进行排序 - 实际上您可以提前执行此操作并丢弃任何重复项。
For each a number
While the smallest pos in the priority queue is <= a
Add the smallest multiple of b to it to make it >= a
If it is == a, you have a match
Update the stored value of pos for that sequence, re-ordering the priority queue
在最坏的情况下，您最终会将每个数字与每个其他数字进行比较，这与简单的解决方案相同，但具有优先级队列和排序开销。但是，当多个 a 数字通过时，较大的 b 值可能在优先级队列中保持未经检查，在这种情况下这样做会更好 - 如果有很多数字要处理并且它们都是不同的，则其中一些必须很大。
于 2012-10-05T04:54:12.653 回答
0
这个答案提到了算法的要点（称为DL，因为它使用“除数列表”）并通过名为 amodb.py 的程序提供详细信息。
设 B 为输入数组，包含 N 个正整数。不失一般性，假设B[i] > K所有i的 B 是升序的。（请注意，x%B[i] < K如果B[i] < K; 和 where B[i] = K，可以报告所有 的对 (B[i], B[j]) j>i。如果 B 最初没有排序，则收取O(N log N)排序成本。）
在算法DL和程序 amodb.py 中，A 是一个数组，其中 K 是从输入数组元素中预减去的。即，A[i] = B[i] - K。请注意，如果a%b == K，那么对于某些j我们有a = b*j + Kor a-K = b*j。也就是说，a%b == Kiffa-K是 的倍数b。此外，如果a-K = b*j和p是 的任何因数b，则p是 的因数a-K。
让从 2 到 97 的素数称为“小因数”。当从某个区间 [X,Y] 中均匀随机选取 N 个数时，N/ln(Y) 量级的数将有不小的因数；相似的数字将具有最大的小因数 2；而下降的比例将有依次变大的最大的小因素。例如，平均 aboutN/97会被 97 整除，约N/89-N/(89*97)被 89 整除但不能被 97 整除等。一般情况下，当 B 的成员是随机的时，具有某些最大小因子或没有小因子的成员列表是 sub-O(N /ln(Y)) 的长度。
给定一个列表 Bd 包含 B 的成员可被最大的小因子p整除，DL测试 Bd 的每个元素与列表 Ad 的元素，A 的那些元素可被p整除。但是给定一个 Bp 的列表 Bp 包含 B 中没有小因素的元素，DL将针对 A 的所有元素测试 Bp 的每个元素。示例：如果N=25、p=13、Bd=[18967, 23231]和Ad=[12779, 162383]，则DL测试是否有任何一个12779%18967, 162383%18967, 12779%23231, 162383%23231为零。请注意，在此示例（以及许多其他示例）中，可以通过注意将测试数量减少一半12779<18967，但 amodb.py 不包括该优化。
DL针对不同的因素制作J不同的列表；J在 amodb.py 的一个版本中，J=25因子集是小于 100 的素数。较大的值J会增加O(N*J)初始化除数列表的时间，但会略微减少O(N*len(Bp))针对 A 的元素处理列表 Bp 的时间。请参见下面的结果。处理其他列表的时间是，这与先前答案方法O((N/logY)*(N/logY)*J)的复杂性形成鲜明对比。O(n*sqrt(Y))
接下来显示的是两个程序运行的输出。在每一组中，第一Found行来自一个朴素的 O(N*N) 测试，第二行来自DL。（注意，如果逐步删除太小的 A 值， DL和 naïve 方法都会运行得更快。）第一个测试的最后一行中的时间比率显示， DL与 naïve 方法的加速比低到令人失望的 3.9。对于那次运行，factors仅包括 25 个小于 100 的素数。对于第二次运行，加速比更好，约为 4.4，factors包括数字 2 到 13 和最多 100 个素数。
$ python amodb.py
N: 10000 K: 59685 X: 100000 Y: 1000000
Found 208 matches in 21.854 seconds
Found 208 matches in 5.598 seconds
21.854 / 5.598 = 3.904
$ python amodb.py
N: 10000 K: 97881 X: 100000 Y: 1000000
Found 207 matches in 21.234 seconds
Found 207 matches in 4.851 seconds
21.234 / 4.851 = 4.377
程序 amodb.py：
import random, time
factors = [2,3,4,5,6,7,8,9,10,11,12,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
X, N = 100000, 10000
Y, K = 10*X, random.randint(X/2,X)
print "N: ", N, " K: ", K, "X: ", X, " Y: ", Y
B = sorted([random.randint(X,Y) for i in range(N)])
NP = len(factors); NP1 = NP+1
A, Az, Bz = [], [[] for i in range(NP1)], [[] for i in range(NP1)]
t0 = time.time()
for b in B:
a, aj, bj = b-K, -1, -1
A.append(a) # Add a to A
for j,p in enumerate(factors):
if a % p == 0:
aj = j
Az[aj].append(a)
if b % p == 0:
bj = j
Bz[bj].append(b)
Bp = Bz.pop() # Get not-factored B-values list into Bp
di = time.time() - t0; t0 = time.time()
c = 0
for a in A:
for b in B:
if a%b == 0:
c += 1
dq = round(time.time() - t0, 3); t0 = time.time()
c=0
for i,Bd in enumerate(Bz):
Ad = Az[i]
for b in Bd:
for ak in Ad:
if ak % b == 0:
c += 1
for b in Bp:
for ak in A:
if ak % b == 0:
c += 1
dr = round(di + time.time() - t0, 3)
print "Found", c, " matches in", dq, "seconds"
print "Found", c, " matches in", dr, "seconds"
print dq, "/", dr, "=", round(dq/dr, 3)
于 2012-10-06T07:40:23.803 回答