如何提高：给定两个整数，返回它们共享的数字位数

Question

我在面试中收到了这个问题：

给定两个整数，返回它们共同拥有的数字数量。

例如，129和431将返回1 - 因为它们都共享数字1，但没有其他数字。95和780将返回0，因为这两个整数没有重叠部分。

我的想法是遍历这些数字，将它们存储到哈希表中，并检查.containsKey。

我的Java解决方案：

public int commonDigits(int x, int y) {
     int count = 0;
     HashTable<Integer, String> ht = new HashTable<Integer, String>();

     while (x != 0) { 
         ht.put(x % 10, "x");
         x /= 10;
     }

     while (y != 0) {
         if ((ht.containsKey(y % 10)) {
             count++;
         }
         y /= 10;
     }

    return count;
}

但是这需要O(n)的空间和O(n+m)的时间，无论如何我能改进这个吗？

- bZhang

---

你可能会发现这篇文章更适合发布于CodeReview，请参考。 - Draken

“(ht.get(y % 10) != "y")” 的意义是什么？它不会起作用（因为字符串比较），而且地图中也从来没有“y”。 - f1sh

是的，你说得对，我会把那部分删除。 - bZhang

即使是 int[10] 也足够了... - Fildor

我投票关闭此问题，因为有codereview.stackexchange.com可以用于“审查工作代码”请求。 - GhostCat

Answer 1

为什么不使用一些简单的位操作呢？

public int commonDigits(int x, int y) {
  int dX = 0;
  while (x != 0) {
    dX |= 1 << (x % 10);
    x /= 10;
  }
  int count = 0;
  while (y != 0) {
    int mask = 1 << (y % 10);
    if ((dX & mask) != 0) {
      count ++;
      dX &= ~mask;
    }
    y /= 10;
  }
  return count;
}

这段代码为x中的每个数字在dX中设置了一个相应的位。第二个循环中，对于x中的每个数字，代码会检查它是否在dX中有条目。如果是，则计数并重置位以避免重复计数（请注意，在您的代码中缺少此功能，请考虑123和141）。显然不使用任何额外的存储空间（如果需要，dX和count可以只是字节）。

请注意，您的解决方案中不需要使用HashTable--您可以使用HasSet或BitSet。

您的代码已转换为使用BitSet，并修复了重复计数问题：

public int commonDigits(int x, int y) {
  int count = 0;
  BitSet ht = new BitSet();

  while (x != 0) { 
     ht.set(x % 10, true);
     x /= 10;
  }
  while (y != 0) {
     if ((ht.get(y % 10)) {
         count++;
         ht.set(y % 10, false);
     }
     y /= 10;
  }
  return count;
}

两个代码片段的作用完全相同，后者只是在比特集合(BitSet)（和嵌入的数组）实例中有一些额外开销。

本文展示了为什么在一般情况下BitSet比布尔数组更好: http://chrononsystems.com/blog/hidden-evils-of-javas-byte-array-byte 编辑:

如果要多次计数相同的数字(从问题的示例中不清楚是否需要)，请使用int数组来存储计数:

public int commonDigits(int x, int y) {
  int count = 0;
  int[] digits = new int[10];

  while (x != 0) { 
     digits[x % 10]++;
     x /= 10;
  }
  while (y != 0) {
     if (digits[x % 10] > 0) {
         count++;
         digits[x % 10]--;
     }
     y /= 10;
  }
  return count;
}

- Stefan Haustein

---

我喊“黑科技”。二进制黑科技。 - user3235832

绝妙的方式！ - Yassin Hajaj

据我所理解，双重计数是需要的 - 112 和 131 应该返回 2。112 和 133 应该返回 1。 - Fildor

@Fildor 从最初提供的示例中，对于这个问题是否是这种情况并不清楚，因此我已经相应地扩展了答案。 - Stefan Haustein

我不同意你的解释。112和131共享数字1，即它们共享1个数字。 - user1196549

@YvesDaoust 是的。但是OP在评论中指出，如果它们共享相同的数字两次，那么应该计为2。因此，112和131共享数字1两次。 - Fildor

Answer 2

以下是最小存储解决方案（使用10字节的数组而不是哈希表）：

public int commonDigits(int x, int y) {
 int count = 0;
 byte[] digits=new byte[10];

 while (x != 0) { 
     digits[x%10] ++;
     x /= 10;
 }

 while (y != 0) {
     if (digits[y % 10] > 0) {
         count++;
         digits[y % 10] --;
     }
     y /= 10;
 }

return count;
}

该解决方案在运行时间上最优，O(n+m)，其中 n 是 x 中数字的数量，m 是 y 中数字的数量。你不能做得比枚举 x 的数字然后枚举 y 的数字更少。

- AhmadWabbi

---

a) Stefan发布了一个非常相似的解决方案。 b) 布尔值不足够，因为需要计算双精度数。 - Fildor

digits 可以是 byte[]，节省存储空间。 - Cheng Chen

@DannyChen 是的，没错，但存储仍然是O(10)。无论如何，我已经改变了答案。谢谢。 - AhmadWabbi

将数据类型更改为 byte 可以节省存储空间，但会显著降低数字可计数的最大次数。 OP 没有为此命名边界，但在生产代码中必须考虑到这一点。 - Fildor

@Fildor 类型byte计数到127。因此，在Java中，直到我们看到一个数字出现超过127次的int，我们才会遇到问题;-) - AhmadWabbi

Answer 3

由于只有10个可能的数字，为什么不只存储一个整数数组呢？对应0-9的每个数字设置一个数组元素。遍历每个数字并增加相应的数组元素。该空间复杂度取决于您如何定义“常量” - 它将始终占用10个单位的空间（在C/C++中将是10个字节，不确定JVM如何实现）。

根据信息守恒原则，您必须遍历两个数字的每个数字（它们是独立的，因此不能从另一个数字推断出一个数字），因此您的时间复杂度仍为O(m + n)。此外，我认为您所说的O(n)实际上是O(log n)，因为这是任何数字表示中的位数。

- user3235832

---

非唯一数字:P请查看注释部分，因此不要将布尔数组存储到'int'数组中 - Yerken

我猜他用 O(n + m) 表示的是数字的位数，而不是数字本身。 - Thomas

@willywonkadailyblah 因为111和11应该返回它们共享2个数字，而使用布尔数组只会得到1个（就像111和1等情况一样）。 - Thomas

@Thomas，更准确的说法应该是O(log n)，因为数字的位数取决于其表示形式（即基数），而数字的值是一个普遍概念。但这只是一个小问题。 - user3235832

@Polygnome 不行，你不能只使用一个整数，因为如果我没记错的话，11和111也应该报告有2个共享数字，而仅仅知道数字是否存在是做不到的。 - Thomas

Answer 4

最多只能共享10位数字。这意味着您不需要像哈希表那样复杂的数据结构，一个数组或位掩码就足够了！您只需迭代第一个数字，并将您遇到的每个数字标记为“true”（在您的位掩码或数组中）。如果您已经发现了每个数字（使用位掩码很容易和便宜），则甚至可以快速返回。然后遍历第二个数字。每次您遇到一个也被标记为真的数字时，增加计数器。如果位掩码包含每个数字，则通过返回数字的长度（其最高指数）来短路，否则在结束时返回计数器。这并不会减少O复杂度，但它可以减少内存占用并为大型数字添加一些短路。例如，如果第一个数字是1234567890，则它将始终与第二个数字共享与第二个数字有小数点相同的数字。

- Polygnome

---

那不符合原帖的非唯一数字要求。根据评论，原帖想在比较111和11时返回2，即两个数字共享2个数字。使用布尔值只能返回1。如果您检查第二个数字中有多少个数字出现在第一个数字中，然后尝试11和111。如果我没有错，原帖仍然想返回2，但在这种情况下，您只能返回1（存在一个唯一共享的数字）或3（111的所有3个数字都出现在11中），这似乎不符合要求。 - Thomas

这不是真的。对于输入111和11，我的建议解决方案将返回2，就像OP建议的那样。请仔细阅读我使用位掩码和计数的内容。这不是对称的，11和111将返回3，但Ops规范并不清楚，Ops演示代码也没有做到这一点。 - Polygnome

请仔细阅读我的评论，因为我已经提到过你可以返回111和11的2，但在11/111的情况下不行 - 我完全知道你在做什么，但正如我所说，我_假设_（从问题以及评论中）他基本上是在寻找某种基数映射的交集（即每个输入数字的最低位基数之和）。 - Thomas

错误，他的要求非常模糊。我刚刚使用了他在代码示例中使用的相同逻辑，因为那似乎是他想要的。你可以任意复杂化整个过程（对我来说，提出的问题也包括数字的位置，但这又是另一回事）。 - Polygnome

Answer 5

哈希表有点大材小用了，只需使用一个由十个标志组成的数组（能否使用按位运算将它们打包成单个整数或保持独立变量取决于您）。

扫描第一个整数并为每个数字提高相应的标志。

扫描第二个整数，并为每个数字重置相应的标志。

返回从1到0的真重置数量。

更新：要处理重复项，需要将标志替换为计数器。

如果两个数字都具有M个数字，则必须查看所有这些数字，以确保时间复杂度为Ω（M）。

空间复杂度的情况欠清晰。这里呈现的所有解决方案都是O（N），其中N是可能的数字数（在十进制基础上为10）。但可以使用O（1）的空间：依次取第一个数字的每个数字，检查是否是第一个数字中的第一个数字（避免计数重复项），然后检查它是否存在于第二个数字中。这是一个O（M²）-时间过程，但仅需要O（1）空间。

更新：要处理重复项，请每次处理数字时计算第一个数字中相同前导符号的数量。在查找第二个数字时，还要匹配先行者的数量。

因此，人们可能会想知道是否有可能实现时间复杂度为O（M），空间复杂度为O（1）的解决方案。

我的解决方案是O（M + N）时间，O（N）空间。时间复杂度中的+N仅需要用于初始化所有N个标志。如果您接受不计算初始化，则可以这样编写算法，以便清除它所设置的所有标志（以便可以再次运行算法），从而产生一个O（M）时间，O（N）空间的解决方案。

有一个容易的O（M Log M）时间，O（M）空间解决方案，通过对数字的两个字符串进行排序并在合并类似步骤中计算相同的数字。如果M与N相比非常小，则可能会有用。

- user1196549

---

"111和11将返回2，因此数字不唯一" - 该问题的发布者评论。 - Fildor

@Fildor：这是在我的回答之后添加的，所以我倾向于忽略它。我认为这并不会对我的评论产生太大影响。特别是，O(M²)时间，O(1)空间的解决方案可以适应处理重复项，并且关于O(M)/O(1)存在性的问题仍然存在。 - user1196549

考虑到你也许想解决这个问题，我只是想提醒你一下。 - Fildor

Answer 6

你的解决方案没有考虑重复项。

# 11, 211 -> 2

你使用哈希表是正确的，它比数组更快。我将在Python中完成此操作，因为打字速度更快...

# Returns an array containing the shared digits
def getShared(num1, num2):
    shared = []
    digits1 = getDigits(num1)
    digits2 = getDigits(num2)
    for digit in digits1:
        if digit in digits2:
            while digits2[digit] > 1 and digits1[digit] > 1:
                digits2[digit] = digits2[digit] - 1
                digits1[digit] = digits1[digit] - 1
                shared += [digit]
            del digits2[digit]
            del digits1[digit]
    return shared

# Given an integer, returns a dictionary with the keys as the digits,
# and the value as the number of times the digit appears
def getDigits(num)
    dict = {}
    while num > 0:
        newDigit = num % 10
        if newDigit not in dict:
            dict[newDigit] = 1
        else:
            dict[newDigit] = dict[newDigit] + 1
    return dict

- Yaelle

---

他不需要重复项，他希望它们被计算。 - Yerken

那么11和211应该返回1，而不是2吗？ - Yaelle

这样输入更快吗？哈希比数组更快吗？ - AhmadWabbi

看看我的答案，告诉我是否有更快的方法。该数组由数字索引。这有点像哈希。 - AhmadWabbi

“你使用哈希表是正确的，它比数组更快”：胡说八道。 - user1196549