在O（log n）时间内计数排序int数组中具有相同数字的数字

Question

我遇到了一个面试问题，要求候选人计算数组中具有相同数字的所有数字。例如：

计算所有与int input=394 int[]arr={1，14，101，349，439，745，934}共享相同数字的数字

该函数将返回3，因为439, 934, 349共享相同的数字。问题是如何在O（log n）时间内解决这个问题？我对Big 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

这个解决方案几乎是O（n），因为与给定的数组大小（n）相比，输入中的位数非常小。

其思想是从每个元素中获得最小可能数，并与输入数的相应值进行比较

public static void main(String []args){

    int input = 394;
    int[] arr = {1, 14, 101, 349, 439, 745, 934};


    int ans = 0;
    int hold = getMin(input);
    for(int i = 0; i < arr.length; i++)
    {
        if(hold == getMin( arr[i] ))
        {
            ans++;
        }
    }
    System.out.println(ans);
}

public static int getMin(int n)
{
    int hold[] = new int[10];
    while( n > 0)
    {
        hold[n % 10]++;
        n /= 10;
    }

    int ans = 0;
    for(int i = 0; i < hold.length; i++)
    {
        while(hold[i] > 0)
        {
            ans = ans * 10 + i;
            hold[i]--;
        }
    }
    return ans;
}

Answer 2

您可以对数组进行预处理以构造Map，方法是通过映射到该规范化表示的数组中的数字的“字符串表示已排序的数字”。在该步骤之后，单个查找是O（1）或O（log（n）），具体取决于所选的映射。甚至有多少数字匹配都没关系，因为您只是返回一个预构造的数组。

因此，查找确实可以非常快地进行。但前提是您要么打折预处理步骤，要么在多次查找中摊销它。

Answer 3

Andy Turner和JB Nizet给出了最好的答案，但不幸的是只是作为评论：

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

1. 计算输入数字的所有排列。有些排列可能是相同的，如果数字有重复的数字，则只取一次。这需要O（1）时间，置换的数量也是O（1）

总的来说，运行时间为O（log n）。

请注意，只有当输入数字的界限很低时，这才可行。如果输入的数字可以有20位数，那么最好使用O（n）方法，除非n非常大。