在数组中查找对,使得%b = k,其中k是给定的整数

Question

这是我遇到的一个有趣的编程难题.由于正整数数组,以及一些K.我们需要找到对(A,B)从数组这样a % b = K.

我有一个幼稚为O(n ^ 2)解决了这个在这里我们可以检查所有对,使得A%B = K.工作但效率低下.我们当然可以做得比这更好吗？任何有效的算法？哦,这不是功课.

Answer 1

对数组和二进制搜索进行排序,或者使用数组中每个值的计数保留哈希表.

对于许多x,我们可以发现最大的y这样x mod y = K的y = x - K.二进制搜索y或在哈希中查找并相应地增加计数.

现在,这不一定是唯一可行的价值.例如,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))哈希表,则会给您一个完整的复杂性(特别推荐您的数字不是很大).