如何改进:给定两个整数,返回它们共享的位数

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)时间,无论如何我可以改进这个？

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;
}

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.