算法笔试题-------对一段英文段落根据单词进行分段，并且根据出现频率排序

本是古典何须时尚 2024-04-01 17:13 64阅读 0赞

## 算法笔试题-------对一段英文段落根据单词进行分段，并且根据出现频率排序 ##

背景：英文段落由、。|，分割，对该短信息根据符号进行分段，并且统计单词出现的频率，根据出现频率排序。
    难点在于：**分割时需要注意转义**、以及**进行排序**
    HashMap实现方法：
    HashMap的实现方法，其实是用了比较器Comparator，这种方法取巧，并没有体现出算法。
    使用map可以解决字符串，和次数的对应关系。

/**
         * String 长字符串，,|||、||、、。！分隔符
         * "a,a,a,a,a,a,bb|bb|bb|bc、ccc、ccc、ccd、dd.dd.dd.dee.ee.ee.fffffff.ggggg.hhhhhh"
         * 统计出现单词个数，并按照顺序由高到低排序
         * @param args
         */
        public  void test(){
        
            String s = "a,a,a,a,a,a,bb|bb|bb|bc、ccc、ccc、ccd、dd.dd.dd.dee.ee.ee.fffffff.ggggg.hhhhhh";
            HashMap<String,Integer> hashMap = new HashMap<>();
            String[] split = s.split("\\,");
            for (int i = 0; i < split.length; i++) {
        
                if (split[i].contains("|")){
        
                    String[] split1 = split[i].split("\\|");
                    for (int j = 0; j < split1.length; j++) {
        
                        if (split1[j].contains("、")){
        
                            String[] split2 = split1[j].split("\\、");
                            for (int k = 0; k < split2.length; k++) {
        
                                if (split2[k].contains(".")){
        
                                    String[] split3 = split2[k].split("\\.");
                                    for (int l = 0; l < split3.length; l++) {
        
                                        if (hashMap.containsKey(split3[l])){
        
                                            Integer times = hashMap.get(split3[l]) + new Integer(1);
                                            hashMap.put(split3[l],times);
                                        }else {
        
                                            hashMap.put(split3[l],new Integer(1));
                                        }
                                    }
                                }else {
        
                                    if (hashMap.containsKey(split2[k])){
        
                                        Integer times = hashMap.get(split2[k]) + new Integer(1);
                                        hashMap.put(split2[k],times);
                                    }else {
        
                                        hashMap.put(split2[k],new Integer(1));
                                    }
                                }
                            }
                        }else {
        
                            if (hashMap.containsKey(split1[j])){
        
                                Integer times = hashMap.get(split1[j]) + new Integer(1);
                                hashMap.put(split1[j],times);
                            }else {
        
                                hashMap.put(split1[j],new Integer(1));
                            }
                        }
                    }
                }else {
        
                    if (hashMap.containsKey(split[i])){
        
                        Integer times = hashMap.get(split[i]) + new Integer(1);
                        hashMap.put(split[i],times);
                    }else {
        
                        hashMap.put(split[i],new Integer(1));
                    }
                }
            }
            List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(hashMap.entrySet());
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        
                    return o2.getValue() - o1.getValue();
                }
            });
            //排序后
            for (int i = 0; i < list.size(); i++) {
        
                String id = list.get(i).toString();
                System.out.println(id);
            }
        }

输出结果：

a=6
    bb=3
    dd=3
    ee=2
    ccc=2
    bc=1
    fffffff=1
    hhhhhh=1
    ccd=1
    dee=1
    ggggg=1

如果需要由低到高进行排序。  
改一句代码即可。

Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        
                    return o1.getValue() - o2.getValue();
                }
            });

### ArraryList实现 ###

使用map可以解决字符串，和次数的对应关系。如果使用 ArraryList就需要创建两个arraryList，一个存放字符串，一个存放次数。通过二者的下标进行关联，随后就进行次数数字的排序，在次数数组排序时，讲字符串数组同步操作即可。此处使用的是冒泡算法，复杂度比较高

public  void test(){
        
            String s = "a,a,a,a,a,a,bb|bb|bb|bc、ccc、ccc、ccd、dd.dd.dd.dee.ee.ee.fffffff.ggggg.hhhhhh";
            ArrayList<String> stringList = new ArrayList();
            ArrayList<Integer> intList = new ArrayList();
            String[] split = s.split("\\,");
            for (int i = 0; i < split.length; i++) {
        
                if (split[i].contains("|")){
        
                    String[] split1 = split[i].split("\\|");
                    for (int j = 0; j < split1.length; j++) {
        
                        if (split1[j].contains("、")){
        
                            String[] split2 = split1[j].split("\\、");
                            for (int k = 0; k < split2.length; k++) {
        
                                if (split2[k].contains(".")){
        
                                    String[] split3 = split2[k].split("\\.");
                                    for (int l = 0; l < split3.length; l++) {
        
                                        if (stringList.contains(split3[l])){
        
                                            //获取下标
                                            int stringIndex = stringList.indexOf(split3[l]);
                                            //出现次数
                                            Integer times = intList.get(stringIndex);
                                            intList.set(stringIndex,times+1);
                                        }else {
        
                                            stringList.add(split3[l]);
                                            int stringIndex = stringList.indexOf(split3[l]);
                                            intList.add(stringIndex,1);
                                        }
                                    }
                                }else {
        
                                    if (stringList.contains(split2[k])){
        
                                        //获取下标
                                        int stringIndex = stringList.indexOf(split2[k]);
                                        //出现次数
                                        Integer times = intList.get(stringIndex);
                                        intList.set(stringIndex,times+1);
                                    }else {
        
                                        stringList.add(split2[k]);
                                        int stringIndex = stringList.indexOf(split2[k]);
                                        intList.add(stringIndex,1);
                                    }
                                }
                            }
                        }else {
        
                            if (stringList.contains(split1[j])){
        
                                //获取下标
                                int stringIndex = stringList.indexOf(split1[j]);
                                //出现次数
                                Integer times = intList.get(stringIndex);
                                intList.set(stringIndex,times+1);
                            }else {
        
                                stringList.add(split1[j]);
                                int stringIndex = stringList.indexOf(split1[j]);
                                intList.add(stringIndex,1);
                            }
                        }
                    }
                }else {
        
                    if (stringList.contains(split[i])){
        
                        //获取下标
                        int stringIndex = stringList.indexOf(split[i]);
                        //出现次数
                        Integer times = intList.get(stringIndex);
                        intList.set(stringIndex,times+1);
                    }else {
        
                        stringList.add(split[i]);
                        int stringIndex = stringList.indexOf(split[i]);
                        intList.add(stringIndex,1);
                    }
                }
            }
            //排序
            for (int i = 0; i < intList.size(); i++) {
        
                for (int j = i+1; j < intList.size(); j++) {
        
                    if (intList.get(i) < intList.get(j)){
        
                        Integer i1 = intList.get(i);
                        Integer i2 = intList.get(j);
                        String s1 = stringList.get(i);
                        String s2 = stringList.get(j);
                        intList.set(i,i2);
                        stringList.set(i,s2);
                        intList.set(j,i1);
                        stringList.set(j,s1);
                    }
                }
            }
            System.out.println(stringList.toString());
            System.out.println(intList.toString());
        }

打印结果如下所示：

[a, bb, dd, ccc, ee, bc, dee, ccd, fffffff, ggggg, hhhhhh]
    [6, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1]