脚本的效率(查找具有相同余数的一对整数)

问题描述

我正在尝试在A中找到一对(x，y)，使得x-y=0(Mod N)，其中输入是一个正整数n，一个由m个非负整数和m>；n组成的集合A。为了运行下面的代码，我取了一个m和n，只是为了运行一个示例。

下面是我写的脚本。

我想知道是否有更有效的方法来编写脚本

import numpy as np import sys

n = 10 
m = 12

def functi(n, m):

  A = [0] * m

  for i in range(m):

    A[i] = np.random.randint(0,34)
   

  X = [-1] * n


  for i in range(len(A)-1,-1,-1) :  #loop backwards
    a = A[i]
    A.pop(i)
    r = a % n

    if X[r] == -1:
      X[r] = a
    else:
     return(X[r], a)
  

pair = functi(n, m) 
print(pair)

---

解决方案

请注意，您的函数没有问题描述的参数--它应该以n和A作为参数，而不是以m并生成自己的A。

如果您简单地将其视为找到一对具有相同值的数字mod n"；，则问题会容易得多。一种简单的方法是根据值% n存储所有数字，并在其中有两个数字时返回一个存储桶。这样，您就不需要逐个比较每对值来查看它们是否匹配。

>>> import random
>>> def find_equal_pair_mod_n(n, A):
...     assert len(A) > n
...     mods = {}
...     for i in A:
...         xy = mods.setdefault(i % n, [])
...         xy.append(i)
...         if len(xy) > 1:
...             return tuple(xy)
...
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(26, 6)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(30, 10)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(32, 32)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(1, 1)
>>> find_equal_pair_mod_n(10, [random.randint(0, 34) for _ in range(12)])
(28, 8)