java - 在 O(log n) 时间内计算排序的 int 数组中具有相同数字的数字

Question

我遇到一个面试问题，要求应聘者计算数组中具有相同数字的所有数字。例如:

用 int input = 394 计算所有具有相同数字的数字int[] arr = {1, 14, 101, 349, 439, 745, 934}

该函数将返回 3，因为 439、934、349 共享相同的数字。问题是如何在 O(log n) 时间内解决这个问题？我对大 O 概念还是陌生的，除了 O(n) 和 O(n^2) 之外……我无法理解如何实现 O(log n)。

我的第一个想法是:我会计算数组中所有元素的数字总和。如果总和相等，则它们包含与输入数字相同的数字。

      int counter = 0;

      while (num > 0) {
         int digitSum += num % 10;
         num = num / 10;
      }
      for(int i = 0; i < arr.length; i++) {
      int k = arr[i];

      while (k > 0) {
          int sumOfDigits += k % 10;
          k = k/10;
      }
      if(sumOfDigits == digitSum) {
       counter++;
      }
}

我知道这至少需要 O(n) 时间，但我找不到更好的解决方案。

Answer 1

最佳答案由 Andy Turner 和 JB Nizet 给出，但遗憾的是仅作为评论:

为此，我们必须假设:输入数字的大小是有界的，数组中的整数是不相交的，n 是数组中元素的数量。

1. 计算输入数字的所有排列。如果数字有重复的数字，一些排列可能是相同的，只取一次。这需要 O(1) 时间，排列数也是 O(1)。
2. 对于每个排列，使用二进制搜索在数组中查找相应的数字并计算所有命中数。这需要 O(log n)。

总的来说你得到了 O(log n) 的运行时间。

请注意，这仅在输入数字的界限相当低时才实用。如果输入数字可以说是 20 位数字，那么使用 O(n) 方法要好得多，除非 n 真的很大。