比嵌套循环更快的算法? [英] Faster algorithm than nested loops?

问题描述

对于Google codeJam资格鉴定，问题之一是查找两个给定整数之间有多少个回收对".

For the google codeJam qualification round one of the problems was finding how many 'recycled pairs' there are between two given integers.

这是我的解决方案，但对于大型数据输入集而言，速度还不够快.给定类似@a = 10，@ b = 200000之类的东西，它开始变慢.

This was my solution but it wasn't fast enough for the large data input set. Given something like @a = 10, @b = 200000 it starts to get slow.

我认为我的解决方案将是O(2 ^ n)(我对大型O分析还没有足够的了解)，这太可怕了.我想知道是否有一种标准的方法可以使用更快的算法遍历这样的两个循环?

I think my solution would be O(2^n) (I don't have a solid grasp on big O analysis yet) which is horrible. I was wondering if theres a standard way to iterate through two loops like this with a faster algorithm?

def getPairs
    (@a..@b).each do |n|
      (n..@b).each do |m|
        if (containsSame(n,m)) && (isMatch(@a, n, m, @b))
          @recycledPairs += 1
        end
      end
    end
  end

来自 Google CodeJam网站:

假设如果您可以通过将一些数字从n的后部移动到前部而不改变其顺序来获得m，那么将回收一对不同的正整数(n，m).例如，(12345，34512)是一个回收对，因为您可以通过将345从12345的末端移到前面来获得34512.请注意，n和m必须具有相同的位数，才能成为可循环使用的对. n和m都不可以带有前导零.

Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

推荐答案

您可以阅读

You can read the official analysis of this problem for the correct solution.

基本上，解决方案是为每个n计算大于n但不大于B的所有不同旋转.

Basically, the solution is to compute all the distinct rotations larger than n, but not larger than B for each n.

这篇关于比嵌套循环更快的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！