我尝试了几种使用集合的解决方案,并使用您提供的示例数组运行了每个解决方案1000万次进行测试:
private static String[] input = {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"};
首先,这是我用来调用这些算法的方法:
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
for (int x = 0; x < 10000000; x++) {
Set<String> confirmedAnagrams = new HashSet<>();
for (int i = 0; i < (input.length / 2) + 1; i++) {
if (!confirmedAnagrams.contains(input[i])) {
for (int j = i + 1; j < input.length; j++) {
if (isAnagrams1(input[i], input[j])) {
confirmedAnagrams.add(input[i]);
confirmedAnagrams.add(input[j]);
}
}
}
}
output = confirmedAnagrams.toArray(new String[confirmedAnagrams.size()]);
}
long endTime = System.currentTimeMillis();
System.out.println("Total time: " + (endTime - startTime));
System.out.println("Average time: " + ((endTime - startTime) / 10000000D));
}
我将使用基于字符哈希集的算法进行翻译。我将每个单词的每个字符添加到哈希集中,如果哈希集的长度不等于初始单词的长度,则它们不是变位词。
我的算法及其运行时间:
算法1:
private static boolean isAnagrams1(String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
Set<Character> anagramSet = new HashSet<>();
for (int i = 0; i < x.length(); i++) {
anagramSet.add(x.charAt(i));
anagramSet.add(y.charAt(i));
}
return anagramSet.size() != x.length();
}
这是运行时间:
Total time: 6914
Average time: 6.914E-4
Algorithm 2
private static boolean isAnagrams2(String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
Set<Character> anagramSet = new HashSet<>();
char[] xAr = x.toCharArray();
char[] yAr = y.toCharArray();
for (int i = 0; i < xAr.length; i++) {
anagramSet.add(xAr[i]);
anagramSet.add(yAr[i]);
}
return anagramSet.size() != x.length();
}
是否已运行:
Total time: 8752
Average time: 8.752E-4
算法3
对于这个算法,我决定将Set传递进去,因此每个循环只创建一次,并在每次测试后清除它。
private static boolean isAnagrams3(Set<Character> anagramSet, String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
for (int i = 0; i < x.length(); i++) {
anagramSet.add(x.charAt(i));
anagramSet.add(y.charAt(i));
}
return anagramSet.size() != x.length();
}
是否运行时间为:
Total time: 8251
Average time: 8.251E-4
算法4
这个算法不是我写的,它属于Pratik Upacharya
,他也回答了这个问题,为了让我进行比较:
private static boolean isAnagrams4(String stringOne, String stringTwo) {
char[] first = stringOne.toLowerCase().toCharArray();
char[] second = stringTwo.toLowerCase().toCharArray();
if (first.length != second.length) {
return false;
}
int[] counts = new int[26];
for (int i = 0; i < first.length; i++) {
counts[first[i] - 97]++;
counts[second[i] - 97]--;
}
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
return false;
}
}
return true;
}
有这个运行时:
Total time: 5707
Average time: 5.707E-4
当然,这些运行时间对于每次测试都是不同的,为了进行适当的测试,需要更大的示例集,以及更多的迭代。*编辑,因为我在初始方法中犯了一个错误,Pratik Upacharya的算法似乎更快。
char[]
转换回String
然后再使用charAt()
。 - QBrute