一道阿里电话面试中的算法题

 

电话面试算法题一道：找出数组中重复次数最多的元素并打印

 

问题不难，看你能给出更优的方案

 

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

import commons.algorithm.sort.QuickSort;

/**
 * 找出数组中重复次数最多的元素并打印
 *
 */
public class Problem_3 {
	
	//先快速排序后循环查找    O( n*log2(n) + n )
	public static void find1(int[] arr){
		
		QuickSort.sort(arr);
		
		
		int max = arr[0];
		int pre=1;
		int now=1;
		
		for(int i=0;i<(arr.length-1);i++){
			
			if(arr[i]==arr[i+1])
				now++;
			else {
				if(now>=pre){
					pre=now;
					now=1;
					max=arr[i];
				}	
			}
		}
		
		
		
	}
	
	//嵌套循环查找   O(n*n)
	public static void find2(int[] arr){
		

		int pre=0;
		int max=arr[0];
		
		for(int i=0;i<arr.length;i++){
			int now=0;
			for(int j=0;j<arr.length;j++){
				
				if(arr[i]==arr[j]) {
					now++;	
				}				
			}
			
			if(now>=pre){			
				max=arr[i];
				pre=now;			
			}
			
					
		}
		
	
		
	}
	
	//通过 Hash 方式
	public static void find3(int[] arr){
		HashMap<Integer,Integer> hm=new HashMap<Integer, Integer>();
		for(int i=0;i<arr.length;i++){
			if(hm.containsKey(arr[i])) {
				int count=hm.get(arr[i]);
				hm.put(arr[i], ++count);
			 
			}else{
				hm.put(arr[i],1);
			}
		}
		
		Iterator<Entry<Integer, Integer>> it=hm.entrySet().iterator();
		int pre=0;
		int max=arr[0];
		while(it.hasNext()) {
			Entry<Integer, Integer> en=it.next();
			int key=en.getKey();
			int val=en.getValue();
			if(val>pre){	
				pre=val;
				max=key;
			}
			
		}
		
	
		
	}
	public static  void main(String args[]){

		//数据量800 重复元素多，查找时候分别是：  46  3680  195
		int arr2[]={0,1,2,        .....       
				,0,1,2,3,6,7,8,9};
		
		//数据量800 重复元素少，查找时间分别是     82  3727  360
		int arr[]={0,0,0,11,12,13,14,5,6    ......     
		                ,51,52,53,,728,29,730,731,3,794,95,796,797,798,799};
		

		
		long start,end;
			
		start=System.currentTimeMillis();
		for(int i=0;i<1000;i++) find1(arr);
		end=System.currentTimeMillis();
		System.out.println(end-start);
		
		start=System.currentTimeMillis();
		for(int i=0;i<1000;i++) find2(arr);
		end=System.currentTimeMillis();
		System.out.println(end-start);
		
		
		start=System.currentTimeMillis();
		for(int i=0;i<1000;i++) find3(arr);
		end=System.currentTimeMillis();
		System.out.println(end-start);
		
	}
}

 

评论

30 楼 sunhj000java 2010-10-07  

我认为这道题的关键是如何遍历这个数据集合，如果能不用遍历集合而找出出现最多的次数的数字是这道题的关键。
我们可以用hashmap保存数据出现的个数，并且用两个变量保存出现最多的次数(max1)和次多的次数(max2)，当剩下的数据个数小于max1-max2，那么我们就找出了这个数字了。
最优为n/2  最差为n

29 楼 worldwalk 2010-10-07  

xjwm 写道

只想问一句， 在项目里面会用到吗？

我倒是感觉笔试面试的题目项目中不会怎么用到，做项目和考试不是一个思路。 所以面试前要多做一些类似的题目，熟悉一下思路

28 楼 zhzhwe 2010-10-07  

int arr[] = { 1, 2, 5, 5, 6, 6, 9, 5, 3, 3, 4, 4, 4, 4, 5, 2, 2, 2, 2,
2, 7, 7, 7, 7, 7, 7 };
//定义MAP KEY表示存放的数字，VALUES表示出现的次数
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : arr) {
if (map.containsKey(n)) {
map.put(n, map.get(n) + 1);
} else {
map.put(n, 1);
}
}
//遍厉MAP
for (Map.Entry<Integer, Integer> m : map.entrySet()) { 
System.out.println(m.getKey() + " 出现了 " + m.getValue() + " 次.");  
   } 
}

27 楼 xiaoyao312 2010-10-07  

电话考察，那可得有足够编程经验和灵活的编程思想才能应付的了啊！

26 楼 0704681032 2010-10-07  

iamlotus 写道

用Hash的各位算过Hash的开销没有？不能光考虑时间复杂度，还要考虑空间复杂度。如果没有更多附加空间怎么办？
既然是电面，首先问明白限制条件，数据量是多大，K/M/G/T?重复数据占比?有没有附加空间/时间要求?
数据量K，随便怎么搞。
数据量M，QuickSort
数据量G，MergeSort了，因为内存不够要用IO
数据量T，MapReduce，否则单机处理不过来

重复数据非常多，考虑用Hash {data->repeatCount}，以空间换时间
重复数据少，还是老老实实排序吧，Hash的空间开销蛮大的，而且resize相当慢。

复杂度分析来说，每个数据至少访问一遍，不可能有比O(n)更好的，这就是个考实现的题。既然是实现，当然要搞清楚环境，哪有闷着头写程序的道理。

说的很有道理...

25 楼 东四环屠夫 2010-10-06  

笔试题都犯不着搞这么长的答案。。 用 HashMap 即可。

电话面试主要是看你能不能干活，问点基础而已，至少基本库要知道吧。

24 楼 grayhound 2010-10-06  

楼上的各位有没有想过map.get()方法的时间复杂度？

23 楼 xjwm 2010-10-06  

只想问一句， 在项目里面会用到吗？

22 楼 笑我痴狂 2010-10-06  

首先要看  数组是不是已经排好序的 

如果是没有排序的   要想想要不要排好序后再去查找

方案一：没有排序的数组 ，用hashMap去存储，key是数组元素，value是出现的次数

方案二：如果是有序数组 ， 只记录当前出现次数最多的数组值 ， 每次去遍历下一个数组值的时候，直接跳过n个（n就是当前出现次数最多的次数），因为是排好序的， 所以在检测下一个值时，先记录下要检测的这个值，然后向后跳跃n-1个，如果跳跃之后的这个值跟你之前记录下的值比较不想等，就说明跳跃过的这几个值中间不可能出现比当前出现次数最多的值还多，这样算下了  时间复杂度就小于O（n） 

21 楼 gundumw100 2010-10-06  

貌似可以采用如下算法，我只是猜想，楼主不妨改改试试。
/**
      * 统计字符出现次数
      * @param s
      */ 
public Map<Character, Integer> getStatistics(String s) {   
        Map<Character, Integer> map = new HashMap<Character, Integer>();   
        int i, size = s.length();   
        for (i = 0; i < size; i++) {   
           char c = s.charAt(i);   
           map.put(c, map.containsKey(c) ? ((Integer) map.get(c) + 1) : 1);   
        }   
              return map; 
} 

20 楼 InsonSiu 2010-10-06  

学习了，在没有看到回复前，我应该会用两个数组去比较，但现在觉得terencewong的方法会更好。

19 楼 flyingpig4 2010-10-06  

iamlotus的说法很有见解

18 楼 iamlotus 2010-10-06  

用Hash的各位算过Hash的开销没有？不能光考虑时间复杂度，还要考虑空间复杂度。如果没有更多附加空间怎么办？
既然是电面，首先问明白限制条件，数据量是多大，K/M/G/T?重复数据占比?有没有附加空间/时间要求?
数据量K，随便怎么搞。
数据量M，QuickSort
数据量G，MergeSort了，因为内存不够要用IO
数据量T，MapReduce，否则单机处理不过来

重复数据非常多，考虑用Hash {data->repeatCount}，以空间换时间
重复数据少，还是老老实实排序吧，Hash的空间开销蛮大的，而且resize相当慢。

复杂度分析来说，每个数据至少访问一遍，不可能有比O(n)更好的，这就是个考实现的题。既然是实现，当然要搞清楚环境，哪有闷着头写程序的道理。

17 楼 bao231 2010-10-06  

首先要搞清楚，面试考的是什么方面的？不要乱提意见

我感觉他的考查点位：循环一次就能找到最大的重复元素。

16 楼 gosin 2010-10-06  

用HashMap就行了。

15 楼 phyeas 2010-10-06  

LZ，要看你的测试数据量…这种题主要时间都花在查找上，hash方式的查找效率是很快的，而其他方式则会受到查找时间的限制

14 楼 phyeas 2010-10-06  

想到最小完美哈希函数，不过生成函数的效率不高…

13 楼 leves 2010-10-06  

<p>
</p>
<pre name="code" class="java">public static void find3(int[] arr){
HashMap&lt;Integer,Integer&gt; hm=new HashMap&lt;Integer, Integer&gt;();
for(int i=0;i&lt;arr.length;i++){
if(hm.containsKey(arr[i])) {
int count=hm.get(arr[i]);
hm.put(arr[i], ++count);

}else{
hm.put(arr[i],1);
}
}

Iterator&lt;Entry&lt;Integer, Integer&gt;&gt; it=hm.entrySet().iterator();
int pre=0;
int max=arr[0];
while(it.hasNext()) {
Entry&lt;Integer, Integer&gt; en=it.next();
int key=en.getKey();
int val=en.getValue();
if(val&gt;pre){
pre=val;
max=key;
}

}

//System.out.println(max);

}</pre>

<p> </p>
<p>用Hash的方式写的，为什么测试的时候速度上反而是最慢的</p>

12 楼 mr_kairy 2010-10-06  

早上刚写的一个。。。贴出来大家评下哈....
效率也不算很高,也就是选择排序的那个效率了。。

		/**
		 * 思路: 依次选择比较。。记录每个数比较过后重复的个数  记录在变量里面..
		 * 然后比较当前 这个数 重复的次数  是否 大于上一次重复的个数。。
		 * 
		 */
		 int arr[] ={1,2,5,5,6,6,9,5,3,3,4,4,4,4,5,2,2,2,2,2,7,7,7,7,7,7};
		 
		 int tempCount = 0;	//记录上个一个数 重复的个数
		 int reNumber[] = new int[50];		//重复需要打印的数
		 
		 //双循环 知道重复的个数...
		 for(int i=0;i<arr.length -1 ; i++){
			
			 int nowCount = 0 ;	//当前这个数 重复的个数
			 
			 for (int j = i+1; j < arr.length; j++) {
				//判断当前循环的数 是否有重复的
				 if(arr[i] == arr[j]){
					 nowCount++;
				 }
			 }
			 
			 //判断 当前 重复的数 是否 多于上一次重复的数
			 if(nowCount > tempCount){
				 tempCount = nowCount;
				 reNumber = new int[50];	//设置50个大小 装重复的数
			 }
			 
			 //如果有相同个数  重复的数
			 if(nowCount == tempCount){
				 for (int j = 0; j < reNumber.length; j++) {
					 if(reNumber[j] == 0){
						 reNumber[j] = arr[i];
						 break;
					 }
				 }
			 }
		 }
		 
		 //打印 
		 for (int i = 0; i < reNumber.length; i++) {
			if(reNumber[i] == 0){
				break;
			}else{
				System.out.println(reNumber[i]);
			}
		}

结果输出:2 , 7

11 楼 leves 2010-10-06  

icanfly 写道

codeparser 写道

terencewong 写道

you can consider hash. Key will be the value of the array element, and the duplicate time will be the value. The complexity will be O(n). Maybe you can do more research to make it in O(lgN).

应该是这个思路，因为它只要求记录最多的那个元素，可以在hash的时候，顺便记录下当前重复次数最多的元素。
有种情况是重复次数相同的时候，也需要记录下来，这样只需要扫描一遍数组就可以了。

有两个值有可能hash值一样，还得做一下判断！

在读的时候通过Hash的方式存，但读的时候呢？不是还需要循环比较 value的大小？