日期:2014-05-20  浏览次数:20833 次

面试的一道算法题
说 :

 有以下字符 [2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7]
有N个字符,请统计哪个字符出现的频率最高

------解决方案--------------------
Java code

大概就是这样
if(map.containsKey(key)){
            int tempNum = map.get(key)+1;
            map.put(key, tempNum);
        }else{
            map.put(key, 1);
        }

------解决方案--------------------
if(map.containsKey(key)){
int tempNum = map.get(key)+1;
map.put(key, tempNum);
}else{
map.put(key, 1);
}

------解决方案--------------------
Java code

package Collection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MapCountNum {
    public static final int ONE = 1;

    public static void main(String[] args) {
        int[] arr = { 2, 3, 6, 4, 3, 5, 3, 3, 3, 6, 0, 9, 6, 2, 2, 3, 9, 1, 5,
                7 };
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i]))
                map.put(arr[i], ONE);
            else {
                int count = map.get(arr[i]);
                map.put(arr[i], count + 1);
            }
        }
        for (int i : map.keySet()) {
            list.add(map.get(i));
            System.out.println(i + "元素出现的个数:" + map.get(i));
        }        
        System.out.println("出现频率最高的是:" + map.get(Collections.max(list)));
         }
}

------解决方案--------------------
采用中序遍历二叉树节点频度实现
//中序遍历一棵二叉树,非递归实现。
int traverse(tree *r)
{
tree *p,*q;
 sqstack l;
 initstack(&l);
 p=r;
 push(&l,p);
 while(p==r||l.base!=l.top)
 {
if(p->left!=NULL)
{
push(&l,p->left);
q=p;
p=p->left;
q->left=NULL;
 
}
else
{
p=pop(&l);
if(n==0)
{
printf("%-6d",sign);
printf("%-20s次数-->",p->a);
printf("%-6d\n",p->i);
}
sum+=p->i;
strncpy(wonu[sign].a,ko,N);
strncpy(wonu[sign].a,p->a,N);
wonu[sign].i=p->i;
sign++;
if(p->right!=NULL)
{
push(&l,p->right);
q=p;
p=p->right;
q->right=NULL;
 
}
 
}
 }
 
 return 0;
}
------解决方案--------------------
我不怎么会用hasmap,所以只好用纯数组的方法写了一个相关的程序,并且已经通过正确的运行,代码如下:
public class helloworld {
public static void main(String[] args) {
int count=0;
int temp=0;
int value=0;
int[] arr = { 2, 3, 6, 4, 3, 5, 3, 3, 3, 6, 0, 9, 6, 2, 2, 3, 9, 1, 5,
7 };
int [] arr1={ 2, 3, 6, 4, 3, 5, 3, 3, 3, 6, 0, 9, 6, 2, 2, 3, 9, 1, 5,
7 };
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr1.length;j++){
if(arr[i]==arr[j]){
temp++;
}
}
if(temp>count){
count=temp;
value=arr[i];
}
temp=0;
}
System.out.println(value+"的出现频率最大,最大频率值为:"+count);
}
}

输出结果:3的出现频率最大,最大频率值为:6

我写的这个简单易懂,比较适合初学者,我想问下,这样写跟8楼那样的哪个执行的效率更高,请高手赐教!!
------解决方案--------------------
Java code

public static void main(String[] args)
    {
        int[] nums = {2, 3, 6, 4, 3, 5, 3, 3, 3, 6, 0, 9, 6, 2, 2, 3, 9, 1, 5, 7};
        
        // 利用Map统计每个元素出现的次数
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            Integer count = map.get(nums[i]);
            
            count = (count == null) ? new Integer(1) : ++count;        
            map.put(nums[i], count);
        }
        
        // 遍历Map,寻找出现次数最大的元素
        int maxNum   = 2;
        int maxCount = 1;
        Set<Entry<Integer, Integer>> entrySet = map.entrySet();
        for (Entry<Integer, Integer> entry : entrySet) {
            int count = entry.getValue();
            if (count > maxCount) {
                maxNum   = entry.getKey();
                maxCount = count;
            }
        }
        
        // 输出出现次数最大的元素及其次数
        System.out.println(maxNum + ": " + maxCount);
    }