0

我有一个非常大的提要文件，其中包含很多列。我将用字符串表示其中一个列，我想检查这些字符串...

让我们看看我们有这些字符串值（在一个列中），提要显然是功能性的:)：

"Gia Joe Black Viper"
"Street Fighter...Ken"
"Mortal Kombat, Scorpion"
"Gia Joe Desert Fox"
"Mortal Kombat, Sub Zero"
"Street Fighter...Ryu"

我想在字符串中找到匹配项......所以为了简化任务是：在另一个字符串中找到一个字符串子字符串并将这些子字符串收集到一个 HashSet 中......

所以基本上结果标签是：

Gi Joe 
Mortal Kombat 
Street Fighter

我写了一个简单的代码来测试算法，但我想最小化这个任务的时间复杂度，空间复杂度没有时间那么重要......（你可以认为像 10.000 行这样的提要，所以它是基本的时间复杂度低）你可以在我的代码下面找到并阅读：

    String[] stringArray = new String[6];
        stringArray[0] = "Mortal Kombat - Scorpion";
        stringArray[1] = "Street Fighter - Ken";
        stringArray[2] = "Mortal Kombat - Scorpion";
        stringArray[3] = "Gi Joe - Desert Fox";
        stringArray[4] = "Gi Joe - Desert Dog";
        stringArray[5] = "Street Fighter - Ryu";

        HashSet<String> commonStrings = new HashSet();

        for (int i = 0; i < stringArray.length; i++) {
            String[] splittedString = stringArray[i].split("[ ]");
            System.out.println("i"+i);
            for (int j = 0; j < stringArray.length; j++) {
                System.out.println("j"+j);
                String matchable = "";
                for (int k = 0; k < splittedString.length; k++) {
                    System.out.println("k"+k);
                    if(k==0)matchable=matchable;
                    else {matchable = matchable + " " + splittedString[k];}
                    if(j!=i){
                        System.out.println("StringArray["+j+"]("+stringArray[j]+")index.of("+matchable+")"+"is"+matchable.indexOf(stringArray[j]));
                        if (stringArray[j].indexOf(matchable) > 0) {
                            commonStrings.add(matchable);
                        }
                    }
                }
            }

任何建议都可以使我的代码更好，谢谢！

4

2 回答 2

2

您的复杂性是二次的，使用这样的哈希图可以是 O(n)：

Map<String, Integer> cout = new HashMap<String, Integer>();

for (String line : StringArray) {
  for (String s : line.split("-")) {
     Integer currentCount = counts.get(s);
     if (currentCount == null)
       counts.put(s, 1);
     else
       counts.put(s, currentCount + 1);
  }
}
//Look in currentCount all keys with a value larger than 1.

else这仍然可以通过改进语句来优化（但不会降低复杂性） ；）。

于 2012-08-22T12:49:09.760 回答
1

您可以拆分和排序单词，而不是遍历这样的排序列表。结果应该是一样的。当然，这只是整个单词检查的解决方案。您可以使用一些专用的数据结构来代替排序。

于 2012-08-22T12:50:16.783 回答