1

所以我正在开发一种算法来计算给定单词中每个字符的重复次数。我正在使用 aHashMap并将每个唯一字符添加到HashMap作为键，值是重复次数。我想知道我的解决方案的运行时间是多少，以及是否有更有效的方法来解决问题。

这是代码：

public static void getCount(String name){
        public HashMap<String, Integer> names = new HashMap<String, Integer>() ;
        for(int i =0; i<name.length(); i++){

            if(names.containsKey(name.substring(i, i+1))){
                names.put(name.substring(i, i+1), names.get(name.substring(i, i+1)) +1);
            }
            else{
                names.put(name.substring(i, i+1), 1);
            }
        }

        Set<String> a = names.keySet();
        Iterator i = a.iterator();

        while(i.hasNext()){
            String t = (String) i.next();
            System.out.println(t + " Ocurred " + names.get(t) + " times");
        }
    }
4

4 回答 4

2

该算法的时间复杂度为O(n)，但我会更改您的实现的某些部分，即：

  • 使用单个get()而不是containsKey()+ get();
  • 使用charAt()代替substring()which 将创建一个新String对象；
  • 使用 aMap<Character, Integer>而不是，Map<String, Integer>因为您只关心单个字符，而不是整个String：

换句话说：

public static void getCount(String name) {
    Map<Character, Integer> names = new HashMap<Character, Integer>();
    for(int i = 0; i < name.length(); i++) {
        char c = name.charAt(i);
        Integer count = names.get(c);
        if (count == null) {
            count = 0;
        }
        names.put(c, count + 1);
    }
    Set<Character> a = names.keySet();
    for (Character t : a) {
        System.out.println(t + " Ocurred " + names.get(t) + " times");
    }
}
于 2012-08-30T03:00:50.810 回答
1

从算法的角度来看，您的解决方案是 O(n)，这已经是最佳的（至少您必须检查整个字符串中的每个字符至少一次，即 O(n)）。

但是，有几种方法可以加快速度，以减少持续的开销，例如

  • 使用HashMap<Character,Integer>. 字符将比长度为 1 的字符串更有效。
  • 使用charAt(i)而不是substring(i,i+1). 这样可以避免创建一个对您有很大帮助的新字符串。可能是您可以做出的最大单一改进。
  • 如果字符串很长（例如数千个字符或更多），请考虑使用int[]数组而不是 HashMap 来计算单个字符，并将字符的 ASCII 值用作数组的索引。如果您的字符串很短，这不是一个好主意。
于 2012-08-30T02:57:09.320 回答
0

将初始时间存储到变量中，如下所示：

long start = System.currentTimeMillis();

然后最后，当你完成时，打印出当前时间减去开始时间：

System.out.println((System.currentTimeMillis() - start) + "ms taken");

看看做这件事所花费的时间。据我所知，这是最有效的方法，但可能还有另一种好方法。此外，对每个单独的字符使用 char 而不是字符串（因为 char/Character 是字符的最佳类，一系列字符的字符串）然后做name.charAt(i)而不是name.substring(i, i+1)将你的 hashmap 更改为 HashMap<Character, Integer>

于 2012-08-30T02:52:21.990 回答
0

字符串 s="好";

    //collect different unique characters 

    ArrayList<String> temp=new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(!temp.contains(""+c))
        {
            temp.add(""+s.charAt(i));

        }

    }

    System.out.println(temp);
    //get count of each occurrence in the string
    for (int i = 0; i < temp.size(); i++) {
        int count=0;
        for (int j = 0; j < s.length(); j++) {

            if(temp.get(i).equals(s.charAt(j)+"")){

                count++;
            }
        }
        System.out.println("Occurance of "+ temp.get(i) + " is "+ count+ " times" );
    }*/
于 2013-01-29T12:52:11.057 回答