以下代码的时间复杂度是多少？

Question

/*
 * Program to group anagrams from the string array input
 */

import java.util.*;

public class StringArrayAnagrams {

    //function to group the anagrams together
    public static void groupAnagrams(String[] inputArray) { 
        Hashtable<String, ArrayList<String>> store = new Hashtable<String, ArrayList<String>>(); //to store the sorted string as keys and words from input array that have same sort string
        if (inputArray.length == 0) { 
            System.out.println("Input array is empty");
            return;
        } else if(inputArray.length == 1) { 
            System.out.println(inputArray[0]);
            return;
        }

        for(String word:inputArray) { 
            char[] temp = word.toCharArray();
            Arrays.sort(temp);
            String tempStr = new String(temp);
            if (store.containsKey(tempStr)) { 
                ArrayList<String> lStore = store.get(tempStr);
                lStore.add(word);
            } else { 
                ArrayList<String> newLStore = new ArrayList<String>();
                newLStore.add(word);
                store.put(tempStr,  newLStore);
            }
        }
        //to print the grouped anagrams
        Set<String> keySet = store.keySet();
        for(String eachKey:keySet) { 
            ArrayList<String> anagramList = store.get(eachKey); 
            System.out.println(anagramList);
        }
    }

    public static void main(String[] args) { 
        String[] input = {"bat", "bta", "cat", "tca", "vish"}; 
        StringArrayAnagrams.groupAnagrams(input);   
    }
}

我编写这段代码是为了将输入字符串数组中的字谜组合在一起并打印出来。我仍在努力学习如何回答代码的时间复杂度。代码的时间复杂度是多少？

Answer 1

这种处理在 Java 8.

中更容易

String[] input = {"bat", "bta", "cat", "tca", "vish"}; 
Collection<List<String>> grouped = Stream.of(input)
          .collect(Collectors.groupBy(w -> sortLetters(w))
          .values();

public static String sortLetters(String w) {
    char[] letters = w.toCharArray();
    Arrays.sort(letters);
    return new String(letters);
}

时间复杂度为 O(n)，其中 n 是单词的数量，假设所有单词的长度大致相同或具有较小的上限。如果单词真的很长，这是 O(N * log N)，其中 N 是单词的长度。

以下代码的时间复杂度是多少？

What is the time complexity of the following code?

java

time

complexity-theory