|
该帖已经被评为新手帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-04-06
今天面试碰到 "1000个0-9的数字,查找出现次数最多的3个数字.并求这他们出现的次数."的题目,大概写了一下.结果是出来了,但是我觉得这样写不好,本人算法很菜,大家有没有更好的解决办法?
package com.yongyou;
import java.util.Random;
/**
* 1000个0-9的数字,查找出现次数最多的3个数字.并求这他们出现的次数.
* @author Administration
*/
public class TestFindMoreTimes {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int nums []= new int[1000];
//初始化数据,产生1000个0~9的数字.
for (int i = 0; i < nums.length; i++) {
Random m = new Random();
nums[i] = m.nextInt(10);//随即产生0-9的数字,然后放入到数组中
}
print(nums);
find(nums);
}
/**
* 查找重复次数最多的3个数
* @param nums
*/
public static void find(int[] nums){
int times[] = {0,1,2,3,4,5,6,7,8,9};
//存放出现的次数数组,数组的下标为0~9中数字.比如: sum[0]=5 表示0出现5次.sum[1]=8 表示1出现8次.依次类推.
int sum [] = new int[times.length];
for (int i = 0; i < times.length; i++) {
int k = 0;
for (int j = 0; j < nums.length; j++) {
if(times[i] == nums[j]){
k++;
}
}
sum[i] = k;
}
findMax(sum);
}
/**
* 打印
* @param nums
*/
public static void print(int[] nums){
for (int i = 0; i < nums.length; i++) {
if(i != nums.length-1){
System.out.print(nums[i]+",");
}else{
System.out.print(nums[i] +"\n");
}
}
}
/**
* 查找数组中最大的三个数
* @param times
*/
public static void findMax(int times[]){
//最大3个数
int max1 = 0,max2 = 0,max3 = 0;
//最多3个次数.
int maxTime1 = 0,maxTime2 = 0,maxTime3 = 0;
print(times);
//查找第一多的
for (int i = 0; i < times.length; i++) {
if(maxTime1 < times[i]){
maxTime1 = times[i];
max1 = i;
}
}
System.out.println("出现次数第一多的数:"+max1+",出现的次数为:"+maxTime1);
//把已经查找过的数据填充为-1
times[max1] = -1;
for (int i = 0; i < times.length; i++) {
if(maxTime2 < times[i] && times[i] != -1){
maxTime2 = times[i];
max2 = i;
}
}
System.out.println("出现次数第二多的数:"+max2+",出现的次数为:"+maxTime2);
//把已经查找过的数据填充为-1
times[max2] = -1;
for (int i = 0; i < times.length; i++) {
if(maxTime3 < times[i] && times[i] != -1){
maxTime3 = times[i];
max3 = i;
}
}
System.out.println("出现次数第三多的数:"+max3+",出现的次数为:"+maxTime3);
}
}
打印结果:
2,4,3,6,9,2,1,9,3,7,4,1,0,1,2,2,1,5,8,8,4,1,1,7,6,1,9,6,5,5,6,9,1,8,7,9,9,1,6,3,4,4,6,5,3,1,1,5,7,7,8,0,1,9,3,5,2,4,4,4,0,8,5,3,2,1,9,6,7,9,8,2,6,4,1,7,2,0,9,1,4,6,6,5,5,6,3,5,3,3,8,3,6,3,1,0,6,2,7,1,8,4,7,3,3,1,3,1,3,7,4,0,9,7,9,4,6,0,2,1,9,2,8,8,0,1,6,4,4,4,0,4,4,3,3,4,9,3,0,3,5,6,3,2,4,7,5,1,3,7,4,4,4,8,5,7,9,8,7,1,3,1,0,7,8,4,6,9,5,2,8,5,2,7,3,8,4,4,6,3,5,9,2,8,9,8,7,1,6,5,1,4,4,1,5,8,7,5,9,0,7,4,6,5,3,6,1,2,9,6,2,1,1,8,4,1,2,6,6,0,0,4,9,0,8,9,5,7,7,2,3,8,4,2,7,8,7,5,3,4,4,6,9,5,0,4,8,7,1,6,3,1,9,7,4,9,0,4,0,3,5,8,0,8,6,7,8,1,0,2,0,8,3,0,1,1,7,6,6,2,2,8,1,7,8,2,5,2,5,8,4,0,0,2,4,2,8,3,4,2,5,6,4,4,8,8,7,2,3,8,0,0,6,4,2,1,6,7,1,5,3,7,1,2,3,4,5,1,8,1,5,1,3,1,8,5,1,0,1,1,8,4,6,2,6,8,0,2,7,4,3,0,8,5,0,1,2,8,1,2,9,0,4,8,5,5,8,1,5,8,9,5,2,9,8,2,2,0,2,6,1,9,0,5,8,4,6,9,1,6,8,0,7,0,3,5,5,9,5,9,9,6,1,9,2,8,2,7,6,8,0,8,7,1,4,2,2,7,6,1,7,0,9,7,6,4,4,3,3,5,7,7,8,9,6,9,6,3,7,6,3,2,5,2,5,8,2,7,1,0,7,7,5,6,8,9,2,3,4,9,6,1,3,9,1,9,0,5,6,7,0,7,6,0,5,3,7,4,5,0,2,1,1,8,2,4,8,4,5,4,8,2,2,6,1,7,0,9,3,1,5,4,0,4,2,9,4,5,4,7,7,0,2,1,7,5,3,5,6,0,7,3,6,5,9,5,4,4,1,6,5,6,1,1,4,2,1,9,7,4,6,3,6,9,1,3,4,0,1,8,1,5,0,3,4,9,3,1,7,8,2,2,2,2,5,1,4,0,2,2,2,1,2,9,9,8,2,9,6,0,4,9,5,2,1,3,7,0,2,5,8,5,0,2,7,0,2,6,2,4,7,6,1,2,3,5,7,5,6,2,1,5,0,2,1,2,3,4,7,8,3,8,0,8,2,5,5,8,0,1,3,3,7,5,9,8,8,1,5,0,5,4,1,9,2,1,0,9,1,0,6,7,8,4,9,7,9,0,0,8,2,5,1,7,0,7,5,8,5,9,6,6,6,3,1,5,0,8,3,0,3,4,8,4,3,3,9,3,0,7,8,9,3,4,5,6,0,9,7,2,1,1,8,4,6,0,3,4,7,4,6,7,9,3,0,3,9,6,9,2,2,2,5,5,9,0,0,6,2,4,1,1,7,6,3,9,5,6,6,6,8,8,1,2,0,4,3,0,9,4,5,4,9,1,7,7,2,1,1,0,0,0,9,3,3,1,9,3,3,7,3,7,1,2,2,6,0,4,8,9,0,7,8,3,8,3,4,1,2,8,1,6,0,1,2,1,9,2,8,3,2,5,8,5,9,3,2,1,6,9,7,6,5,3,0,1,4,4,2,8,4,4,2,0,9,0,7,7,7,6,4,0,6,9,2,4,7,2,3,9,9,8,3,8,3,8,1,3,6,9,8,5,8,1,4,2,0,2,9,4,2,7,6,1,9,6,3,0,4,1,8,1,3,4,5,2,0,5,5,3,8,0,9,0,1,3,4,8,1,5,0,9,6,5,0,7,2,8,2,3,2,9,9,2,4,7,0,8,6,4,0,8,6,8,3,6,6,7,5,3,0,1,3,7,1,6,3,8,4,5,4,1,2,9,0,5,7,1,7,1,2,9,3,8,1,2,7,5,3,8,7,1,7,3,0,8,2,9,6,8,6,0,9,9,5,4,3,8,1,2,2,2,2,3,9,8,5,5,5,5,2,9,8,8,1,3,0,1,1,9,3,7,7,7,2,2,3,6,3,7 96,118,112,101,100,95,90,94,102,92 出现次数第一多的数:1,出现的次数为:118 出现次数第二多的数:2,出现的次数为:112 出现次数第三多的数:8,出现的次数为:102
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-04-06
findMax
这个方法是不是有点复杂啊？ 直接用最基本的冒泡排序将数字从大到小排序，然后取出前三个应该可以吧？ LZ程序看起来挺清晰的 |
| 返回顶楼 | |
|
发表时间：2011-04-06
一个大loop循环nums
一个switch 0-9 判断 然后分别加到对应值上面 取最大3个数 直接对times[]进行排序 然后取前三个就是了 |
| 返回顶楼 | |
|
发表时间：2011-04-06
稍微改进一下吧，查找的时候没必要双重循环
public static void find(int[] nums){
int times[] = {0,1,2,3,4,5,6,7,8,9};
//存放出现的次数数组,数组的下标为0~9中数字.比如: sum[0]=5 表示0出现5次.sum[1]=8 表示1出现8次.依次类推.
int sum [] = new int[times.length];
for (int i = 0; i < times.length; i++) {
int k = 0;
for (int j = 0; j < nums.length; j++) {
if(times[i] == nums[j]){
k++;
}
}
sum[i] = k;
}
findMax(sum);
}
用一次循环就OK了 public static void find(int[] nums){
//存放出现的次数数组,数组的下标为0~9中数字.比如: sum[0]=5 表示0出现5次.sum[1]=8 表示1出现8次.依次类推.
int sum[] = new int[10];
for (int j = 0; j < nums.length; j++) {
sum[nums[i]]++;
}
findMax(sum);
}
|
| 返回顶楼 | |
|
发表时间：2011-04-06
简单写下，抛砖引玉
package com.zhaozh.test;
import java.util.*;
/**
* Created by IntelliJ IDEA.
* User: zhaozh
* Date: 11-4-6
* Time: 下午9:54
*/
public class FetchLargestNum {
// 1000个0-9的数字,查找出现次数最多的3个数字.并求这他们出现的次数
private static final int NUMS = 1000;
private static final int LARGEST_Ned = 3;
public static void main(String[] args){
int[] nums = generateNums();
for(int i=0;i<NUMS;i++)
System.out.println(nums[i]);
Map<Integer,List<Integer>> map = findLagestNum(nums);
printResult(map);
}
private static void printResult(Map<Integer, List<Integer>> map) {
Set<Integer> keys = map.keySet();
int index = 0;
for(Integer key : keys){
if (index<LARGEST_Ned) {
System.out.println(map.get(key) + ":" + key);
index++;
}
}
}
private static Map<Integer,List<Integer>> findLagestNum(int[] nums) {
Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.get(nums[i]) == null)
map.put(nums[i],1);
else
map.put(nums[i],map.get(nums[i])+1);
}
return reverseMap(map);
}
private static Map<Integer, List<Integer>> reverseMap(Map<Integer, Integer> map) {
Map<Integer, List<Integer>> rtmap = new TreeMap<Integer, List<Integer>>(Collections.<Object>reverseOrder());
Set<Integer> keys = map.keySet();
for(Integer key : keys){
if(!rtmap.containsKey(map.get(key))) {
List<Integer> list = new ArrayList<Integer>();
list.add(key);
rtmap.put(map.get(key),list);
}else{
rtmap.get(map.get(key)).add(key);
}
}
return rtmap;
}
private static int[] generateNums() {
int[] rans = new int[NUMS];
Random random = new Random();
for(int i=0;i<NUMS;i++)
rans[i] = random.nextInt(10);
return rans;
}
}
|
| 返回顶楼 | |
|
发表时间：2011-04-06
不错，Bag大概就是这么实现的。
|
| 返回顶楼 | |
|
发表时间：2011-04-06
哈哈，重庆的，哈哈，同同同。
|
| 返回顶楼 | |
|
发表时间：2011-04-06
新手帖都18个了
|
| 返回顶楼 | |
|
发表时间：2011-04-06
import random
a = [] for i in range(1000): a.append(random.randint(0, 9)) b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in range(len(a)): b[a[i]] += 1 for j in range(1, 4): max = 0 index = 10 for i in range(len(b)): if b[i]>max: max = b[i] index = i b[index] = -1 print "num " + str(index) + 'has the '+str(j) +'th times: ' + str(max) python版本的 ，这个题目不难啊 :-)，很多方法的 实在是不想用自带的sort了。 |
| 返回顶楼 | |
|
发表时间：2011-04-07
最后修改：2011-04-07
/**
* @author 蛋疼,统计一批数中个数最多的
*
*/
public class TestMax {
// 初始化数据
private static void initData(int[] nums) {
for (int i = 0; i < nums.length; i++) {
Random m = new Random();
nums[i] = m.nextInt(10);// 随即产生0-9的数字,然后放入到数组中
System.out.print(nums[i] + "-");
}
System.out.println();
}
// 统计各个数字出现的次数
public static Map<Integer, Integer> count(int[] nums) {
Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
int count = 1;
if (numMap.containsKey(nums[i])) {
count = numMap.get(nums[i]).intValue() + 1;
numMap.put(nums[i], count);
} else {
numMap.put(nums[i], count);
}
}
return numMap;
}
// 排序map
public static void sort(List<Entry<Integer, Integer>> list) {
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> o1,
Map.Entry<Integer, Integer> o2) {
return (o2.getValue() - o1.getValue());
}
});
}
// 打印
public static void printResult(List<Entry<Integer, Integer>> list, int num) {
System.out.println("=====================打印前" + num
+ "个数的统计====================");
for (int i = 0; i < num; i++) {
Entry<Integer, Integer> e = list.get(i);
System.out.println(e.getKey() + "的个数为：" + e.getValue());
}
}
// 蛋疼啊
public static void main(String[] args) {
int total = 100;
int nums[] = new int[total];
// 初始化
initData(nums);
// 统计
Map<Integer, Integer> m = count(nums);
List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(
m.entrySet());
// 排序
sort(list);
// 前3个结果
printResult(list, 3);
// 所有的结果
printResult(list, m.size());
}
}
result: 9-1-9-2-2-6-2-4-7-9-2-3-4-4-6-3-8-5-0-2-7-6-1-3-0-1-0-9-6-1-9-4-5-7-2-3-8-1-9-8-9-4-4-9-9-9-9-5-6-8-2-6-7-2-5-6-3-0-7-9-1-5-6-7-9-0-4-9-4-0-0-2-0-9-8-3-1-9-7-6-3-4-3-4-6-9-1-6-9-1-9-9-7-8-2-7-5-7-4-9- =====================打印前3个数的统计==================== 9的个数为：21 4的个数为：11 6的个数为：11 =====================打印前10个数的统计==================== 9的个数为：21 4的个数为：11 6的个数为：11 2的个数为：10 7的个数为：10 1的个数为：9 0的个数为：8 3的个数为：8 5的个数为：6 8的个数为：6 |
| 返回顶楼 | |
