面试的一道算法题

Question

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

Answer 1

有一个笨方法
用hashMap来存，然后如果key相同的就往value+1

Answer 2

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

Answer 3

if(map.containsKey(key)){
            int tempNum = map.get(key)+1;
            map.put(key, tempNum);
        }else{
            map.put(key, 1);
        }

Answer 4

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)));
         }
}这是我写的测试程序，楼主可以试一下 ，不知符合楼主要求不？
思路是这样的：先用Map来存储并记录各元素出现的次数，再用List存储各元素出现的次数，然后求得其中次数最大的，再返回次数最大的Key值，就是出现频率最高的元素！

Answer 5

采用中序遍历二叉树节点频度实现
//中序遍历一棵二叉树，非递归实现。
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;
}

Answer 6

很早以前用C写de实现,楼主自己理解以下,用JAVA实现.这是时间复杂度最低的算法了

Answer 7

HashMap统计字符的个数，一边统计一边记住最大值和字符，然后最后一个就是最多出现的字符

Answer 8

我表示先排序  然后再扫过去 代价是N*lg(N)

Answer 9

我不怎么会用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楼那样的哪个执行的效率更高，请高手赐教！！

Answer 10

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);
}

Answer 11

用一个HashMap存储,在存储过程中同时存储字符出现的次数，同时获取数字；看代码：
public class CharCount {
public static void main(String[] args){
int[] chars={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>();
int max=0;
for(int i=0;i<chars.length;i++){
Integer value=map.get(chars[i]);
if(value==null){
map.put(chars[i], 1);
}
else{
if(value>max)max=chars[i];
map.put(chars[i], value+1);
}
}
System.out.println("出现频率最高的是：" + max);
}
}

Answer 12

public class Test {
    public static void main(String[] args) {
        String s = "............";
        int[] cnt = new int[10];
        for(int i=0; i<s.length(); i++) {
            cnt[s.charAt(i)-'0']++;
        }
        for(int i=0; i<cnt.length; i++) {
            if(cnt[i] != 0)
                System.out.println(i + "=" + cnt[i]);
        }
    }
}
  借鉴了人家的思路！贴下，希望对LZ有用。

Answer 13

public static void main(String[] args) {
char[] a={'2','3','6','4','3','5','3','3',};
find(a);
}
public static char find(char[] ch){
Map<Character,Integer> map = new HashMap<Character,Integer>();


for(int i =0 ;i<ch.length;i++){
Integer count = map.get(ch[i]);
if(!map.containsValue(ch[i])){ map.put(ch[i], count==null?1:++count);
}
}
System.out.println(map);
Integer i =Collections.max(map.values());



Iterator<Character> it =map.keySet().iterator();
while(it.hasNext()){
char c = it.next();
if(i==map.get(c)){

System.out.println("出现频率最多的是："+c);
return c;
}

}
return 0;
}

Answer 14

hashmap是一个方法， 但是我觉得不如用array,因为如果是字符的话，毕竟是有限的， 但是这个字符是有什么规律的吗， 如果单纯是数字那就是0-9,就10个元素的char数组就解决了。 我不知道面试官原意是否和楼主表达的一样。如果数组无限大， 那可能就有别的方法了。

Answer 15

那个ArrayList纯粹多余，在遍历输出每个字符的频率的循环中完全可以拿来做一个频率比较，找出最高的那个字符。其实这个题目的算法步骤就两步：1、统计每个字符出现的频率；2、遍历频率表返回频率最高的字符。

Answer 16

int a[]={2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};
int b[];//存放比较次数
int count;
int i;
int j;
for(i=0;i<a.length;i++)
{
 count=0;
 for(j=0;j<a.length;j++)
 {
  if(a[i]==a[j])
  {
   count=count+1;
  }
 }
 b[i]=count;
}
count=0;
for(i=0;i<a.length-1;i++)
{
 for(j=i;j<a.length;j++)
 {
  if(b[i]<b[j])
  {
   count=a[j];
  }
  else
  {
   count=a[i];
  }
 }
}

Answer 17

这种问题我首先想到正则import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class CopyOfCopy_3_of_Test {
public static void main(String[] args) {
Integer c[]=new Integer[]{2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};
Arrays.sort(c) ;
String str = "";
for(int i = 0 ; i<c.length;i++){
str+=c[i];
}
Matcher m = Pattern.compile("\\G(\\d)\\1*").matcher(str);
while(m.find()){
System.out.println(m.group(1)+":"+m.group().length());
}
}
}
0:1
1:1
2:3
3:6
4:1
5:2
6:3
7:1
9:2

Answer 18

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;/**
 * 类说明：统计一篇文章中每个字符出现的次数(实现方法 ： 采用map来实现)
 * 
 * @author 作者: LiuJunGuang
 * @version 创建时间：2011-4-22 下午04:32:19
 */
public class CharCount {
private Map<Character, Integer> map = new HashMap<Character, Integer>(); public void charCount(String str) {
char c = '\0';
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else
map.put(c, 1);
}
Iterator ite = map.entrySet().iterator();
System.out.println("字符\t次数");
while (ite.hasNext()) {
Entry entry = (Entry) ite.next();
System.out.println(" " + entry.getKey() + "\t" + entry.getValue());
}
} public static void main(String[] args) throws Exception {
CharCount cc = new CharCount();
StringBuffer sb = new StringBuffer();
FileReader fr = new FileReader("src/test2/说明.txt");// 要读取的文章的路径
BufferedReader br = new BufferedReader(fr);
String str = "";
while ((str = br.readLine()) != null) {
sb.append(str);
}
cc.charCount(sb.toString());
br.close();
fr.close(); }}

Answer 19

package com;import java.util.*;public class CountNumber {

//假设的数组 
public static final int[] arrays = {2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};

//最大数
public static int max = 0;

public static void main(String[] args){

//定义一个map对象统计每个数出现的次数 
Map<Integer, Integer> maps = new HashMap<Integer, Integer>();

//遍历数组
for(int i=0; i<arrays.length; i++)
{
//如果在map中没有键为下标为 i的数组元素 执行 
if(!maps.containsKey(arrays[i]))
maps.put(arrays[i], 1);
else {
int value = maps.get(arrays[i]);
maps.put(arrays[i], value + 1);
}
}

//输出所有统计数 
for(Integer i : maps.keySet())
{

System.out.println(i + "\t" + maps.get(i));
 
if(maps.get(i) > max)
max = i;
}

System.out.println("Max number is " + max);

}

}

Answer 20

package com;import java.util.*;public class CountNumber {

//假设的数组 
public static final int[] arrays = {2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};

//最大数
public static int max = 0;

public static void main(String[] args){

//定义一个map对象统计每个数出现的次数 
Map<Integer, Integer> maps = new HashMap<Integer, Integer>();

//遍历数组
for(int i=0; i<arrays.length; i++)
{
//如果在map中没有键为下标为 i的数组元素 执行 
if(!maps.containsKey(arrays[i]))
maps.put(arrays[i], 1);
else {
int value = maps.get(arrays[i]);
maps.put(arrays[i], value + 1);
}
}

//输出所有统计数 
for(Integer i : maps.keySet())
{

System.out.println(i + "\t" + maps.get(i));
 
if(maps.get(i) > max)
max = maps.get(i);
}

for(Integer i : maps.keySet())
{
int number = maps.get(i);
if(number == max)
{
max = i;
break;
}
}

System.out.println("Max number is " + max);

}

}

Answer 21

很仓促出来的东西,希望有所帮助:public class Do {
/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
//原始数据
String[] arrS={"2","3","6","4","3","5","3","3","3","6","0","9","6","2","2","3","9","1","5","7"};
//String[] arrS={"1"};
//数据长度
int len = arrS.length;
//最大出现次数
int maxCount=0;
//最大出现字符集
String[] maxCountS=new String[len];
String[] maxCountSClean = maxCountS; 
int maxCountSTag=0;
int tempCount = 1;
for(int i=0,j=1;i<len;j++){
//主要是为了兼容多个字符或者全部字符出现次数一样,使代码臃肿了不少
//时间比较仓促,没有优化
//后面的注释也来不及写了,凑合下
if(i==len-1){
j=i;
}
if(arrS[i].equals(arrS[j])){
tempCount++;
} if(j==len-1){
if(i==j) tempCount--;
System.out.println("字符"+arrS[i]+"出现"+tempCount+"次");
if(maxCount<tempCount){
maxCount = tempCount;
maxCountS = maxCountSClean;
maxCountSTag = 0;
maxCountS[maxCountSTag]= arrS[i];
}else if(maxCount==tempCount){
maxCountS[++maxCountSTag]= arrS[i];
}
tempCount=1;
i++;
j=i;
}
}
System.out.print("最大出现字符是:");
for(int i=0;i<len;i++) {
if(null==maxCountS[i]) break;
System.out.print(maxCountS[i]+"  ");
}
System.out.println("出现次数: "+maxCount);
}}

Answer 22

9楼的通过二叉搜索树的方法挺好的，如果前面出现过就在树中，没出现过的会新建一个结点，每查找一次会增加树中频度，而查找过程的时间复杂度也很低，要是用AVL平衡树更好

Answer 23

假设只有一个最多出现的数：
 int[] arr = { 2, 3, 6, 4, 3, 5, 1, 5, 7,3,1,3 ,3};
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int max = -1;
        int maxTimes = 0;
        for (int i: arr) {
            Integer n = map.get(i);
            map.put(i, n==null ? 1 : n+1 );
            if(map.get(i) > maxTimes){
                maxTimes = map.get(i);
                max = i;
            }
        }
        System.out.println(String.format("Max %s appears %s times.", max, maxTimes));

Answer 24

静态数据没必要放AVL。因为把数组放到AVL也有代价，然后再以对数级算法来查找，这样代价比较大。

Answer 25

 * @author bill
 */
public class NewClass1 {    public static void main(String[] args) {
        int[] ins =new int[] {2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};
//        int[] ins =new int[] {2,3,8,6};
        int[] count=new int[10];
        for(int i=0;i<ins.length;i++){
            System.out.println(""+ins[i]);
                count[ins[i]]=count[ins[i]]+1;
        }
        for(int i:count){
            System.out.print(i+" ");
        }
    }}树叶和树叉很难,我不懂

Answer 26

        int[] ins =new int[] {2,3,6,4,3,5,3,3,3,6,0,9,6,2,2,3,9,1,5,7};
        int[] count=new int[10];
        for(int i=0;i<ins.length;i++){
                count[ins[i]]=count[ins[i]]+1;
        }
        int idx=0;
        for(int i:count){
            System.out.print(idx++ +":"+i+"个, ");
        }

Answer 27

如果  字符很大例如数字2^64，只有几个数，难道要开一个这么大的数组来映射？
我的想法是用一个快排处理排序，然后扫一次，就出来了算法时间复杂度是排序+扫一次的的复杂度，n*log(n)，算法的空间复杂度是N  

Answer 28

这个应该可以了吧，有必要用Map吗