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

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

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

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

		/**
		 * 思路: 依次选择比较。。记录每个数比较过后重复的个数  记录在变量里面..
		 * 然后比较当前 这个数 重复的次数  是否 大于上一次重复的个数。。
		 * 
		 */
		 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

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;
			}
			
		}
		
		//System.out.println(max);
		
	}

 

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

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

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

用HashMap就行了。

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

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

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

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

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

iamlotus的说法很有见解