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

 

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

 

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

 

 

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

 

评论

10 楼 rockis 2010-10-06  

不同的情况有不同的算法。听到这个问题后，应该首先确定数组中的元素是什么类型。是对象，基本类型还是字符串？
如果基本类型或者字符串，建一个hash表即可。如果是对象，还需要确定这个对象是否覆写了hashcode和equals方法。

9 楼 sam_chi 2010-10-06  

这道题应该主要是来考察哈希表的使用

8 楼 icanfly 2010-10-06  

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值一样，还得做一下判断！

7 楼 Lewis·Lee 2010-10-06  

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).

赞成 “terencewong”！

6 楼 ywgoal 2010-10-06  

将该数组tostring（如果是对象则按照一定的规则tostring），然后取到数组里面的每个元素tostring后，到前面那个string中进行split，split后数组length最大的那个就是的了。

5 楼 codeparser 2010-10-06  

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的时候，顺便记录下当前重复次数最多的元素。
有种情况是重复次数相同的时候，也需要记录下来，这样只需要扫描一遍数组就可以了。

4 楼 terencewong 2010-10-06  

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).

3 楼 mengtianheng 2010-10-06  

我觉的是不是可以多定义两个数组，一个放元素，一个放次数，不排序直接接受后对比，如果有了，对应另一个数组相应地方加1（初始0），没有则放到放元素的数组中，最后对比次数，元素也相应找到了。是不是和楼上想的一样，初学，不知道效率高不高。

2 楼 quxiaoyong 2010-10-06  

只想到了最普通的方法：遍历一次数组，用map把数组的值和出现的次数存放起来。然后比较。

1 楼 leves 2010-10-05  

感觉以上两种实现效率上并不高，因为紧张在电话里也没答好。。。