黑马程序员技术交流社区

标题: 写出算法和数据结构 [打印本页]

---

作者: 刘健    时间: 2012-8-4 22:24
标题: 写出算法和数据结构
有一篇英文文章，要统计出中间出现的不重复的英文单词，尽量性能和效率高

---

作者: 黑马__李龙    时间: 2012-8-4 22:34
先利用流来读取英文文章，然后以非字母为分隔符分割出各个单词，比较单个字符以确定是否为不同单词，将读出的不同单词放入一个特殊的字符串中（利用StringBuffer），利用正则表达式搜索这个特殊的字符串（已存储的不同单词）来判断是否和已存储的不同，另外设置不同单词数的计数器计数。（个人觉得正则表达式搜索应该比Map快）

---

作者: 余明辉    时间: 2012-8-5 02:08


代码中用的那一大串英文，是把2楼的那段话，用google翻译了一下，呵呵。。

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class CountEng {

        public static void main(String[] args) {
                String str = "The first stream to read the article in English, " +
                                "and then to the non-alphanumeric delimiter to split each word, " +
                                "comparing a single character to determine whether different words, " +
                                "will read out the word into a special string, use regular expressionsSearch this " +
                                "special string to determine whether stored in different, " +
                                "another set of different words the number of counter";
               
                HashMap<String,Integer> map = new HashMap<String,Integer>();
                String reg = "\\b(\\w)+\\b";
               
                Pattern p = Pattern.compile(reg);
                Matcher m = p.matcher(str);
               
                int num = 0;

                while(m.find()) {
                        String s = m.group();
                        if(map.get(s) == null) {
                                num = 1;
                        } else {
                                num++;
                        }
                        map.put(s, num);
                }
               
                for(Map.Entry<String, Integer> i : map.entrySet()) {
                        System.out.println(i);
                }
        }

}
主要就是通过正则去匹配，然后存到map中去，将单词作为key，出现的次数作为value。
这个是我能想出的唯一一个最快的做法了。高手来指点下

---

作者: 瞿乐    时间: 2012-8-5 02:21
不知道做。。。大神级题目，看也看不懂 - -|||

---

作者: 瞿乐    时间: 2012-8-5 02:21
不知道做。。。大神级题目，看也看不懂 - -|||

---

作者: 黑马__李龙    时间: 2012-8-5 09:29


早起过来看这个帖子，发现自己把这个问题想得过于复杂了，其实很简单，
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashSet;
import java.util.Set;

public class Count {

        public static void main(String[] args) {
                FileReader fs;
                try {
                        fs = new FileReader("English.txt");
                        BufferedReader br = new BufferedReader(fs);
                        Set<String> set = new HashSet<String>();
                        StringBuffer sb = new StringBuffer();
                        int c = 0;
                        // 利用流读取单个字符
                        while ((c = br.read()) != -1) {
                                // 大写字母
                                if (c > 64 && c < 91) {
                                        // 转换成小写字母
                                        c += 32;
                                        sb.append((char) c);
                                        // 小写字母
                                } else if (c > 66 && c < 123) {
                                        sb.append((char) c);
                                        // 非字母
                                } else {
                                        if (sb.length() != 0) {
                                                set.add(sb.toString());
                                                sb = new StringBuffer();
                                        }
                                }
                        }
                        // 关闭流
                        br.close();
                        System.out.println(set.size());
                         // 打印出来
                         for(String str : set){
                              System.out.println(str);
                        }
                } catch (Exception e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                }
        }
}

其中这道题比较影响性能的部位，个人觉得是在判断是否为不同的单词，利用Set本身的方法就可以轻松解决，因为向Set里添加已有的元素String,Set的Size是不会发生改变的。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2