java - 需要提高解决方案性能的输入

Question

我创建了以下逻辑来查找 2 个字符串的组合是否至少包含一次 0-9 的所有数字。但我认为这是非常幼稚的，需要在性能上进行改进。您能否提出更好的解决方案以及我的解决方案有什么问题。谢谢。

输入:带数字的字符串数组(例如:012345,6789,34567)。我试图找出有多少对字符串至少包含一次所有数字 0-9。(在示例中:1 对 -1st 和 2nd)。

static long getNumberOfValidPairs(String[] tickets) {
        long count=0;
        for(int i=0;i<tickets.length-1;i++){
           for(int j=i+1;j<tickets.length;j++){
               String concat = tickets[i]+tickets[j];
               if(concat.length() <10){
                   continue;
               }
               if(concat.contains("0") && concat.contains("1") && concat.contains("2") && concat.contains("3") && concat.contains("4") && concat.contains("5") && concat.contains("6") && concat.contains("7") && concat.contains("8") && concat.contains("9")){
                   count++;
               }
           }
       }
        return count;
    }

改进的解决方案:

static long getNumberOfValidPairs(String[] tickets) {
        long count=0;
        short[] masks = new short[tickets.length];
        char[] chs = null;
        short mask = 0;
        short mask_full = (short) 0b1111111111;
        for(int i=0;i<tickets.length;i++){
            chs = tickets[i].toCharArray();
            mask = 0;
            for(char ch:chs){
                if (ch >= '0' && ch <= '9') {
                int digit = ch - '0';
                mask |= (1 << digit);
            }

            }
            masks[i] = mask;
        }

        for(int i=0;i<tickets.length-1;i++){
            short mask_i = masks[i];
           for(int j=i+1;j<tickets.length;j++){
               short mask_j = masks[j];
               short mask_i_j_concatenated = (short) (mask_i | mask_j);
            if (mask_i_j_concatenated == mask_full) {
               // System.out.println("Strings [" + string_i + "] and [" + string_j + "] form a pair.");
                count++;
            }
           }
       }
        return count;
    }

Answer 1

我认为这里的时间复杂度是 O(n^2) 因为您需要尝试所有对。所以两个 for 循环就可以了。

所以基本上您唯一可以改进的是检查两个字符串是否成对。目前，您正在通过连接然后搜索每个 0-9 数字来完成此操作。这不是最佳选择，因为您创建了不必要的字符串并搜索每个数字，基本上扫描字符串 10 次。

您可以做的是为每个字符串创建一个位掩码，其中 i 位置的位显示字符串中是否存在 i。然后你可以通过简单的 OR-ing 两个位掩码检查连接是否包含所有数字并检查结果是否为 2^10-1 即 1023。因为你只需要计算一次位掩码和 |操作速度很快，这比连接和扫描数字要好。

一些代码。假设我们有一个字符串列表如下:

    List<String> strings = Arrays.asList("012345","6789","34567");

这是创建位掩码的方式:

    short[] masks = new short[strings.size()];
    for (int i = 0; i < strings.size(); i++) {
        String str = strings.get(i);
        char[] chs = str.toCharArray();
        short mask = 0;
        for (int index = 0; index < chs.length; index++) {
            char ch = chs[index];
            if (ch >= '0' && ch <= '9') {
                int digit = ch - '0';
                mask |= (1 << digit);
            }
        }
        masks[i] = mask;
    }

这是检查配对的方式:

    short mask_full = (short) 0b1111111111;

    for (int i = 0; i < strings.size() - 1; i++) {
        String string_i = strings.get(i);
        short mask_i = masks[i];

        for (int j = i; j < strings.size(); j++) {
            String string_j = strings.get(j);
            short mask_j = masks[j];

            short mask_i_j_concatenated = (short) (mask_i | mask_j);
            if (mask_i_j_concatenated == mask_full) {
                System.out.println("Strings [" + string_i + "] and [" + string_j + "] form a pair.");
            }
        }
    }

我只是草拟了代码，没有做太多验证，所以要小心。