08年千橡的笔试题目

现在校内网的一千万个用户的名字组成的一个文件，其中每行为一个名字，其中很多的名字是重复多次出现。一个名字重复次数越高，说明最常见，设计一个算法，把最常见的100个名字及重复次数以降序列出。
其他算法：1.先设计一个好的散列函数，用一个hash表存储所有用户名和出现次数，再应用堆排序，输出前100个用户。先HASH，统计完后， 建立一个100个元素的堆，一个一个更堆的最小元素比较就可以了
2.一个人的名字大体三字  占六个字节  1千万也就60M
内存完全够 
我设计 数据结构
struct person
{
  char *name;
  int n;
  struct person *next;
}
占内存16个字节  200个不重复的  共占内存32M
这样 就组成了一个链表
往里面插入数据的时候 比较n的大小 决定是不是让这个节点前移。保证链表是从大到小排列的。这样前一百个就是要找的人的名字

再者  可以节省一些移动比较次数：可以用两个链表，期中一个链表保持顺序从大到小，另一个仅是记录次数而已。这样每读入一个人，就寻找，不存在就插入第二个链表，存在 相应n加一，跟第一个链表的尾指针n比较，大于的话就把他插入到第一个链表，第一个链表的尾放到第二个链表。

第三个方法：减少寻找次数  hash存储那最大的一百个，其他的跟第二种方法一样！！

代码实现如下：但是没有实现map集合按映射值排序，排序有时间大家可以细细研究
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class xiaonei {

private static String line="";
private static Map m=new HashMap();
static Iterator it=null;
static int value=1;
public static void main(String args[])
{
try
{
BufferedReader reader=new BufferedReader(new FileReader("D:/10-17编程/xiaonei.txt"));
while((line=reader.readLine())!=null)
{
if(m.containsKey(line))
{
value=Integer.parseInt(m.get(line).toString());
m.remove(line);
m.put(line,++value);
}
else
{
m.put(line,1);
}
}
it=m.entrySet().iterator();
while(it.hasNext())
{
Map.Entry me=(Map.Entry)it.next();
System.out.print(me.getKey());
System.out.println(me.getValue());
}
}
catch(Exception e)
{
e.printStackTrace();
}
finally
{
m.clear();
}

}



}
排序可以参考下面的
Map 按值排序 (Map sort by value) - Java
Map是键值对的集合，又叫作字典或关联数组等，是最常见的数据结构之一。在java如何让一个map按value排序呢？ 看似简单，但却不容易！

比如，Map中key是String类型，表示一个单词，而value是int型，表示该单词出现的次数，现在我们想要按照单词出现的次数来排序：



Map map = new TreeMap();

map.put("me", 1000);

map.put("and", 4000);

map.put("you", 3000);

map.put("food", 10000);

map.put("hungry", 5000);

map.put("later", 6000);




按值排序的结果应该是：




key value

me 1000

you 3000

and 4000

hungry 5000

later 6000

food 10000



首先，不能采用SortedMap结构，因为SortedMap是按键排序的Map，而不是按值排序的Map，我们要的是按值排序的Map。

Couldn't you do this with a SortedMap?

No, because the map are being sorted by its keys.






方法一：



如下Java代码：


import java.util.Iterator;import java.util.Set;import java.util.TreeSet;public class Main {    public static void main(String[] args) {        Set set = new TreeSet();        set.add(new Pair("me", "1000"));        set.add(new Pair("and", "4000"));        set.add(new Pair("you", "3000"));        set.add(new Pair("food", "10000"));        set.add(new Pair("hungry", "5000"));        set.add(new Pair("later", "6000"));        set.add(new Pair("myself", "1000"));        for (Iterator i = set.iterator(); i.hasNext();)            System.out.println(i.next());    }}class Pair implements Comparable {    private final String name;    private final int number;    public Pair(String name, int number) {        this.name = name;        this.number = number;    }    public Pair(String name, String number) throws NumberFormatException {        this.name = name;        this.number = Integer.parseInt(number);    }    public int compareTo(Object o) {        if (o instanceof Pair) {            int cmp = Double.compare(number, ((Pair) o).number);            if (cmp != 0) {                return cmp;            }            return name.compareTo(((Pair) o).name);        }        throw new ClassCastException("Cannot compare Pair with "                + o.getClass().getName());    }    public String toString() {        return name + ' ' + number;    }}




类似的C++代码：





typedef pair<string, int> PAIR;



int cmp(const PAIR& x, const PAIR& y)


{


    return x.second > y.second;


}



map<string,int> m;

vector<PAIR> vec;




for (map<wstring,int>::iterator curr = m.begin(); curr != m.end(); ++curr)


{


    vec.push_back(make_pair(curr->first, curr->second));


}

sort(vec.begin(), vec.end(), cmp);









上面方法的实质意义是：将Map结构中的键值对（Map.Entry）封装成一个自定义的类（结构），或者直接用Map.Entry类。自定义类知道自己应该如何排序，也就是按值排序，具体为自己实现Comparable接口或构造一个Comparator对象，然后不用Map结构而采用有序集合（SortedSet, TreeSet是SortedSet的一种实现)，这样就实现了Map中sort by value要达到的目的。就是说，不用Map，而是把Map.Entry当作一个对象，这样问题变为实现一个该对象的有序集合或对该对象的集合做排序。既可以用SortedSet，这样插入完成后自然就是有序的了，又或者用一个List或数组，然后再对其做排序（Collections.sort() or Arrays.sort()）。



Encapsulate the information in its own class. Either implement
Comparable and write rules for the natural ordering or write a
Comparator based on your criteria. Store the information in a sorted
collection, or use the Collections.sort() method.







方法二：


You can also use the following code to sort by value:




    public static Map sortByValue(Map map) {        List list = new LinkedList(map.entrySet());        Collections.sort(list, new Comparator() {            public int compare(Object o1, Object o2) {                return ((Comparable) ((Map.Entry) (o1)).getValue())                        .compareTo(((Map.Entry) (o2)).getValue());            }        });        Map result = new LinkedHashMap();        for (Iterator it = list.iterator(); it.hasNext();) {            Map.Entry entry = (Map.Entry) it.next();            result.put(entry.getKey(), entry.getValue());        }        return result;    }    public static Map sortByValue(Map map, final boolean reverse) {        List list = new LinkedList(map.entrySet());        Collections.sort(list, new Comparator() {            public int compare(Object o1, Object o2) {                if (reverse) {                    return -((Comparable) ((Map.Entry) (o1)).getValue())                            .compareTo(((Map.Entry) (o2)).getValue());                }                return ((Comparable) ((Map.Entry) (o1)).getValue())                        .compareTo(((Map.Entry) (o2)).getValue());            }        });        Map result = new LinkedHashMap();        for (Iterator it = list.iterator(); it.hasNext();) {            Map.Entry entry = (Map.Entry) it.next();            result.put(entry.getKey(), entry.getValue());        }        return result;    }

                Map map = new HashMap();        map.put("a", 4);        map.put("b", 1);        map.put("c", 3);        map.put("d", 2);        Map sorted = sortByValue(map);        System.out.println(sorted);


// output : {b=1, d=2, c=3, a=4}



或者还可以这样：


        Map map = new HashMap();        map.put("a", 4);        map.put("b", 1);        map.put("c", 3);        map.put("d", 2);        Set<Map.Entry<String, Integer>> treeSet = new TreeSet<Map.Entry<String, Integer>>(                new Comparator<Map.Entry<String, Integer>>() {                    public int compare(Map.Entry<String, Integer> o1,                            Map.Entry<String, Integer> o2) {                        Integer d1 = o1.getValue();                        Integer d2 = o2.getValue();                        int r = d2.compareTo(d1);                        if (r != 0)                            return r;                        else                            return o2.getKey().compareTo(o1.getKey());                    }                });        treeSet.addAll(map.entrySet());        System.out.println(treeSet);        // output : [a=4, c=3, d=2, b=1]




另外，Groovy 中实现 sort map by value，当然本质是一样的，但却很简洁 :

用 groovy 中 map 的 sort 方法（需要 groovy 1.6），

def result = map.sort(){ a, b -> 

            b.value.compareTo(a.value)

        }

如：

["a":3,"b":1,"c":4,"d":2].sort{ a,b -> a.value - b.value }

结果为： [b:1, d:2, a:3, c:4]



Python中也类似：

h = {"a":2,"b":1,"c":3}

i = h.items() // i = [('a', 2), ('c', 3), ('b', 1)]

i.sort(lambda (k1,v1),(k2,v2): cmp(v2,v1) ) // i = [('c', 3), ('a', 2), ('b', 1)]