1000个0-9的数字,查找出现次数最多的3个数字.并求这他们出现的次数.

zhanwc

浏览: 403680 次
性别:
来自: 重庆

最近访客更多访客>>

guoyunsky

huqiao1220

wjywjy

317422638

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

java

面试 J#Python 算法 IDEA

今天面试碰到 "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

分享到：

OperaMasks | 重构！！！！

2011-04-06 21:41
浏览 5492
评论(19)
论坛回复 / 浏览 (19 / 7688)
分类:编程语言
查看更多

19 楼 shdsb 2011-06-16

public class Test {
public static void main(String[] args) {
Random random = new Random();
int[] num = new int[1000];
for (int i = 0; i < 1000; i++) {
int result = random.nextInt(10);
num[i] = result;
}

int count = 0;
int[] max = new int[10];
for (int j = 0; j < 10; j++) {
for (int z = 0; z < num.length; z++) {
if (num[z] == j) {
count++;
max[j] = count;
}
}
System.out.println(j + "出现过" + count + "次");
count = 0;
}

for (int i = 0; i < max.length - 1; i++) {
for (int j = 0; j < max.length - i - 1; j++) {
if (max[j] < max[j + 1]) {
int temp = max[j];
max[j] = max[j + 1];
max[j + 1] = temp;
}
}
}

for (int k = 0; k < 3; k++) {
System.out.println(max[k] + " ");
}
}
}

也写了一个，不知道对不对。忘了注释！

18 楼 jerome-peng 2011-05-27

hubeen 写道

稍微改进一下吧，查找的时候没必要双重循环

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

应该是sum[nums[j]]++;

17 楼 rogetsun 2011-05-26

为什么不在生成1000个随机数（读取1000个随机数）的时候就做点手脚？而非要查找呢？

16 楼 shoth 2011-05-24

把数字和个数加入到Map中
然后对Map进行倒序排序，输出前3个

import java.util.*;
import java.util.Map.*;

public class FindMore {
	public static void main(String[] args) {
		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的数字,然后放入到数组中
		}
		Map<Integer, Integer> maps = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			if (maps.get(num)==null) {
				maps.put(num, 1);
			}else{
				maps.put(num, maps.get(num)+1);
			}
		}
		List<Map.Entry<Integer, Integer>> li = new ArrayList<Map.Entry<Integer,Integer>>(maps.entrySet());
		Collections.sort(li, new Comparator<Map.Entry<Integer, Integer>>() {

			@Override
			public int compare(Entry<Integer, Integer> o1,
					Entry<Integer, Integer> o2) {
				// TODO Auto-generated method stub
				return o2.getValue()-o1.getValue();
			}

		});
		for (int i = 0; i < 10; i++) {
			System.out.println(li.get(i));
		}
	}
}

结果：
1=112
0=110
6=106
8=103
7=99
3=97
9=97
2=95
5=92
4=89

15 楼 549265480 2011-04-20

#include "stdafx.h"

#include "stdafx.h"
#include"iostream"
#include "time.h"

#define NUM 20

typedef int type ;
using namespace std;

struct All
{
int data;
int num;
};

int _tmain(int argc, _TCHAR* argv[])
{
int a[NUM];
All c[10];
for(int i=0;i<10;i++)
{
c[i].data=i;
c[i].num=0;
}
cout<<"数组为"<<endl;
for(int i=0;i<NUM;i++)
{
a[i]=rand()%10;
}

for(int i=0;i<NUM;i++)
{
cout<<"a["<<i<<"]="<<a[i]<<endl;
c[a[i]].num++;
}
    cout<<"统计每个字符出现的位置："<<endl;
    for(int i=0;i<10;i++)
{
cout<<c[i].data<<":"<<c[i].num<<endl;

}

return 0;
}

14 楼 bureaucrat 2011-04-07

这样行不行

List zero = new ArrayList();
zero.add(0);

targetList.removeAll(zero);
int countZero = 100 - list.size();

13 楼 adri1 2011-04-07

咋能把算法写成这样呢....find这么写就可以了

    public static void find(int[] nums){
        int sum [] = new int[10];  
        for (int i : nums) {  
            sum[i]++;
        }  
        findMax(sum);  
    }

12 楼 jorneyR 2011-04-07

    public static void main(String[] args) {
    }

11 楼 william_ai 2011-04-07

有些细节问题要注意下的。例如：
如下表，1、2、3、4，排名前4位的数，出现的次数是相同的（只要存在排在第3位和第4位数字的次数相同就满足条件），怎么取3个呢？

数字	次数
1	101
2	101
3	101
4	101

如不考虑以上问题，第一反应是这么玩：

sort -n t.dat | uniq -c | sort -rn | head -n 3

10 楼 horse88sky 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

9 楼 passionke 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了。

8 楼 ericslegend 2011-04-06

新手帖都18个了

7 楼 jorneyR 2011-04-06

gooooooooooooooooooooooooog

6 楼 sebatinsky 2011-04-06

哈哈，重庆的，哈哈，同同同。

5 楼 heyanglove 2011-04-06

不错，Bag大概就是这么实现的。

4 楼 jobar 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;
    }
}

3 楼 hubeen 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);   
    }

2 楼 congdepeng 2011-04-06

一个大loop循环nums
一个switch 0-9 判断然后分别加到对应值上面

取最大3个数直接对times[]进行排序然后取前三个就是了

1 楼 s929498110 2011-04-06

findMax
这个方法是不是有点复杂啊？
直接用最基本的冒泡排序将数字从大到小排序，然后取出前三个应该可以吧？

LZ程序看起来挺清晰的

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论