如何改进：给定两个整数，return 它们共享的位数

Question

面试时收到这个问题，问题是

Given two integers, return the number of digits that they share.

例如 129 和 431 将 return 1 - 因为它们共享数字 1，但没有其他数字。 95 和 780 将 return 0，因为 none 的整数重叠。

我的想法只是遍历数字，将它们存储到哈希表中并检查 .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) space 和 O(n + m) 的时间，无论如何我可以改进它？

Answer 1

既然只有 10 个可能的数字，为什么不直接存储一个整数数组呢？从 0-9 索引，每个数字一个。遍历每个数字并递增相应的数组元素。 space 的复杂性取决于您定义的 "constant" - 这将始终占用 10 个单位的 space （在 C/C++ 中将是 10 个字节，而不是确定 JVM 是如何做到的）

通过信息守恒，你必须循环遍历两个数字的每个数字（它们是独立的，所以你不能只从另一个推断出一个），所以你的时间复杂度将保持在 O(m + n)。另外我认为 O(n) 你的意思是 O(log n)，因为这是数字的任何表示中的位数。

Answer 2

为什么不使用一些简单的位摆弄呢？

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 和计数可以只是字节）。

请注意，您的解决方案中不需要哈希表——您可以只使用 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;
}

Answer 3

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

# 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

Answer 4

最多可以共享 10 个数字。这意味着您不需要像 Hashtable 这样复杂的数据结构，一个数组或位掩码就足够了！

您只需遍历第一个数字，您点击的每个数字都标记为 "true"（在您的位掩码或数组中）。如果您已经找到每个数字一次（使用位掩码既简单又便宜），您甚至可以尽早将它和 return 短路。然后检查第二个数字。每次你击中一个也被标记为 true 的数字时，增加计数器。如果位掩码包含每个数字，则通过 return 数字的长度（其最高指数）短路，否则 return 末尾的计数器。

这不会降低 O 复杂性，但会减少内存占用并为大数添加一些短路。

例如，如果第一个数字是 1234567890，那么它与第二个数字的位数总是一样多，因为第二个数字有小数位。

Answer 5

这是你的最小存储解决方案（一个 10 字节的数组而不是散列 table）：

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.

的数字

Answer 6

散列 table 有点矫枉过正，只需使用包含十个标志的数组（无论您是通过按位运算将它们打包成单个整数还是保留独立变量都取决于您）。

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

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

Return 真正重置的次数（从 1 到 0）。

更新: 处理重复，flags需要用counter替换。

如果两个数都是M位数，则必须全部查看，这样时间复杂度肯定在Ω(M)。

space 复杂性的情况不太清楚。此处提供的所有解决方案都是 O(N)，其中 N 是可能的数字位数（十进制为 10）。但是 O(1) space 是可能的：依次取第一个数字的每个数字，检查它是否是第一个数字中的第一个这样的数字（以避免重复计数），然后检查它是否存在于第二个数字中数字。这是一个 O(M²) 时间的过程，但仅 O(1)-space。

Update：处理重复，每处理一个数字，统计第一个数字中相同前辈的个数；在第二个数中查找匹配时，也匹配前任数。

所以有人可能想知道 O(M) 时间，O(1)-space 的解决方案是否可能。

我的解决方案是 O(M+N)-时间，O(N)-space。时间复杂度上的+N只需要初始化所有N个标志。如果你接受不计算初始化，你可以这样写算法，它清除所有它设置的标志（这样算法可以再次播放）并且这会产生 O(M)-时间，O( N)-space解.

有一个简单的 O(M Log M)-时间，O(M)-space 解决方案，通过对两个数字串进行排序并在类似合并的步骤中计算相同的数字。如果 M 与 N 相比非常小，则可以使用。

如何改进：给定两个整数，return 它们共享的位数

How to improve: Given two integers, return the number of digits that they share

java

algorithm

int

hashtable