面试的一道算法题
说 :
有以下字符 [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); }
[解决办法]
用一个HashMap存储,在存储过程中同时存储字符出现的次数，同时获取数字；看代码：
- Java code
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); }}
[解决办法]
- Java code
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]); } }}
[解决办法]
- Java code
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; }
[解决办法]
[解决办法]
- Java code
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]; } }}
[解决办法]
这种问题我首先想到正则
- Java code
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()); } }}
------解决方案--------------------
- Java code
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(); }}
[解决办法]
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);
}
}
[解决办法]
- Java code
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); } }
------解决方案--------------------
很仓促出来的东西,希望有所帮助:
- Java code
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); }}