毛毛虫和树叶。我们能比O(n*c)更好吗？

Question

毛毛虫和树叶。我们能比O(n*c)更好吗？

10

发现这个问题是在准备面试时遇到的。

假设一些毛毛虫从底部开始跳到下一个叶子上。它们在跳跃前吃掉了这片叶子。我们有一个代表毛毛虫跳跃步数的数组。如果数组是[2,4,7]，那么它意味着毛毛虫[0]将吃叶子2,4,6..，毛毛虫[1]将吃叶子4,8,12..，而毛毛虫[2]将吃7,14,21...0表示地面。计算未被吃掉的叶子数量。

让我们假设，如果当前叶子已经被吃掉，毛毛虫会跳到下一个目的地。这意味着，如果毛毛虫[7]发现叶子28已被吃掉，它将继续吃35号叶子。

设c为毛毛虫的数量，n为叶子的数量。

显然，暴力解决方案是为每个毛毛虫迭代大小为n的bool数组，并在吃掉叶子后将其标记为true或false。它需要O(n*c)的时间。我们能做得更好吗？

- Hoxeni

1

任何叶子节点的编号不是给定数组中任何数字的倍数，都应该保持未被吃掉的状态。 - Abhishek Bansal

你可能想要使用容斥原理。 - anatolyg

@user1990169 是的，我明白问题简化为你刚才所说的陈述。那么问题就转化为如何找到不是任何数字的倍数的数字的最佳方法。 - Hoxeni

5个回答

3

关于您提到的O(n*c)算法，实际上如果仔细看应该是O(n logc)。

一只毛毛虫会吃掉所有它“跳跃步长”j的倍数的叶子，因此如果它独自一人，每只毛毛虫将会吃掉floor(n/j)片叶子。

这种复杂度受以下界限：

n+n/2+n/3+...+n/c <= n log(c)

虽然c很小，但这也不会有任何影响，只是想指出一下 :)

请查看此链接以获取Cimbali的Inclusion-exclusion实现：figure out Uneaten Leaves algorithm bug

编辑： 这里是调和级数受log(c)界限的证明。我们使用积分下限的不等式。

enter image description here

- Kartik Raj

你方程中的 c 是什么？n + n/2 + ... + n/c 等于 n(1 + 1/2 + ... + 1/c)，而 1 + 1/2 + ... + 1/c 是调和级数，这个级数是发散的，不存在任何极限调和级数。请提供你推导出的公式的证明。 - Pham Trung

c表示问题中提到的不同步骤的数量或毛毛虫的数量。我已经添加了一个编辑，说明了该公式的证明。 - Kartik Raj

0

如果c < n，那么它可能是O(c^2)时间，这会更好。

public class JumpingCaterpillars {
  public static int getUneatenCount(int n, int... steps) {

    //no steps i.e. no caterpillars
    if(steps.length == 0){
      return n;
    }

    Arrays.sort(steps);

    if(steps[0] <= 0){
      throw(new IllegalArgumentException("steps should be positive"));
    }

    //all leaves will be eaten
    if(steps[0] == 1){
      return 0;
    }

    //remove duplicates and multiplies
    LinkedHashSet<Integer> normalizeSteps = new LinkedHashSet<>();

    for(int step : steps){
      if(!isMultiply(step, normalizeSteps)) {
        normalizeSteps.add(step);
      }
    }

    int nonEaten = n;

    for(int step : normalizeSteps){
      nonEaten -= getEatenWithStep(n, step);
    }

    /* increase nonEaten number considering caterpillar coincidences on the same leaf
    (when one caterpillar with step stepOne makes it times equal to another caterpillar stepTwo
    and vice versa)*/
    for(int stepOne : normalizeSteps){
      for(int stepTwo : normalizeSteps){
        if(stepOne < stepTwo){
          nonEaten += getEatenWithStep(n, stepOne * stepTwo);
        }
      }
    }
    return nonEaten;
  }

  private static boolean isMultiply(int candidate, Set<Integer> oldSet){
    for(int element : oldSet) {
      if(candidate % element == 0){
        return true;
      }
    }
    return false;
  }

  private static int getEatenWithStep(int n, int step){
    return step > n ? 0 : n / step;
  }
}

- BigFinger

1

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

0

这只是对@cimbali建议的方法进行的优化。从包含毛毛虫步幅的数组中，您可以删除该数组中步幅值的倍数，以减少找到的组合数量。

例如24片叶子和[2,3,4]毛毛虫跳跃步骤。

第一步：遍历步幅数组并删除2的倍数。由于4是2的倍数，因此从数组中删除4
第二步：大小为1的子集。毛毛虫j=2将单独吃掉24/2 = 12片叶子毛毛虫j=3将单独吃掉24/3 = 8片叶子
第三步：大小为2的子集。毛毛虫j=2和j=3都想吃24/6 = 4片叶子：{6, 12, 18, 24}

所以24-16（12+8-4）= 8片叶子剩下。

- Mudits

0

复杂度不能是O(N)甚至O(N/K)。我的算法是O(2^K)，这本身就很大但仍然可以接受。即使我传递N = Long.MAX_VALUE，我也能立即得到结果。虽然如果K更大，当所有跳跃值的LCM超过Long.MAX_VALUE时，代码可能需要更长时间或代码可能会中断。

为了解释它，让我们取A = {4, 5, 6}和N = 20。

我们可以计算未吃掉的叶子为{1, 2, 3, 7, 9, 11, 13, 14, 17, 19} = 10

如何在不计数的情况下获得此结果？ N - (N / 4) - (N / 5) - (N / 6) + (N / 20) + (N / 12) + (N / 30) - N / 60 = 20 - 5 - 4 - 3 + 1 + 1 + 0 - 0 = 20 - 12 + 2 = 10

毛毛虫未吃叶子问题

- Deepak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cimbali · Accepted Answer

一只毛毛虫会吃掉所有距离为“跳跃步长”j的倍数的叶子，因此如果只有一只毛毛虫，那么每只毛毛虫将吃掉floor(n/j)个叶子。

现在你需要找出哪些叶子被多次计数。例如，如果你为第一只毛毛虫计算了所有能被2整除的叶子，则不必再为第二只毛毛虫计算任何叶子，因为它每隔4个跳跃步长才会吃掉一片叶子。

对于两个毛毛虫，这些重复计数的数字是它们的最小公倍数的倍数，这样的数字有floor(n/lcm(j,j'))个。

请注意，对于三个以上的跳跃步长，如果按照上述方法计算，可能会重复删除某些叶子：以28为例，它会被跳跃步长为7的毛毛虫吃掉，但是却为两只其他毛毛虫都计数（因为28 % 4 == 28 % 2 == 0），因此需要加回被多次删除的倍数：floor(n/lcm(j,j',j"))。

你可以看到这里有一个模式，它是容斥原理。通用公式如下：

inclusion-exclusion formula

令Aj表示一只毛毛虫独自吃掉的跳跃步长为j的叶子集合。然后对于多只毛毛虫跳跃步长的集合J，A_J是所有这些毛毛虫都会吃掉的叶子集合。

AJ is the intersection of the Aj where j is in J

同时，定义集合的最小公倍数为集合中所有元素的最小公倍数，我们可以写成lcm(J)。

[n]在包含-排除公式中是考虑的毛毛虫跳跃的集合，因此在您的情况下为[2,4,7]，我们会遍历它的所有子集。|J|是子集的大小，|A_J|是J中每个毛毛虫可能吃掉的叶子数，所以我们得到|A_J| = floor(n/lcm(J))。

现在您有2的次幂的总和，因为那是只毛毛虫子集的数量。请注意，您可以通过保存最小公倍数而不是从头重新计算来节省一些时间。

我把写实际代码 "作为练习"留给你们，因为有些人喜欢说：基本上就是迭代子集并计算最小公倍数，然后将其全部放入上面的总和中。

这将使您获得所消耗的总叶片数。从这里获取未被吃掉的叶子非常简单。

如果我们在一个小例子上做一下（以便能够检查），其中0为地面，1..24为叶子，[2,3,4]为毛毛虫跳跃步骤。

唯一幸存的叶子将是{1、5、7、11、13、17、19、23}：删除所有偶数和所有可被3整除的数字。也就是说，我们希望答案为8。

第一轮：大小为1的子集。
- 毛毛虫j=2单独吃12片叶子
- 毛毛虫j=3单独吃8片叶子
- 毛毛虫j=4单独吃6片叶子
第二轮：大小为2的子集。

毛毛虫j=2和j=3都想吃24/6 = 4片叶子: {6, 12, 18, 24}
毛毛虫j=3和j=4都想吃24/12 = 2片叶子: {12, 24}
毛毛虫j=4和j=2都想吃24/4 = 6片叶子: 所有被4吃的都是2的目标

第三轮：大小为3的子集：所有毛毛虫一起
- 他们都想吃24/lcm(2,3,4)=24/12 = 2片叶子: {12,24}.
最终轮：已经吃掉12 + 8 + 6 - 4 - 2 - 6 + 2 = 26 - 12 + 2 = 16片叶子

所以还剩下24 - 16 = 8片叶子。

* 当然，这是最坏情况。希望您迭代逐渐增加的子集，并且只要子集J的最小公倍数大于n，您就可以忽略所有的J的超集。特别地，如果所有大小为k的子集的lcm都大于n，则可以停止迭代。