【面试题】不用map,求出现频率超过总数一半的数字

今天药忘吃喽~ 2022-08-07 15:57 114阅读 0赞

有一个整数的数组，求出现频率超过总数一半的数字，没有找到，则返回-1  如：  
  
\[1,2\] => -1  
\[1,1,2,3\] => -1(没有超过一半，总数4，出现2次，没有超过一半)  
\[2,1,2\] => 2 (总数3，2出现了2次，超过了一半)  
  
不要用map,用算法的方式做  
  
当然了，最简单的方法是先排序，做法如下：

public static int getAppearBySort(final int[] arr)
    	{
    		Arrays.sort(arr);
    	    int halfLen = arr.length / 2;
    	    int half = arr.length % 2 == 0 ? (halfLen - 1) : halfLen;
    	    for(int i = 0; i <= half; i ++) 
    	    {
    	        if(arr[i] == arr[i + halfLen]) 
    	        {
    	        	return arr[i];
    	        }
    	    }
    	    return -1;
    	}

如果纯用算法实现，做法如下：

public static int getAvgMax(int[] arr)
    	{
    		int len = arr.length;
    		int nums = len/2;
    		int count;
    		int k;
    		/**
    		 * 最多找len-nums次
    		 */
    		for(int i=0; i<len-nums; i++)
    		{
    			count = 1;
    			/**
    			 * 这里的K是为了减少查找次数的，第一次，最多只找前一半的，没找到，就不用找的
    			 * 第二次是从第二个（第一个不符合要求）开始查找，最多只找前一半-1个，没有找到，就不用找了
    			 * 依次继续
    			 */
    			k = len-nums-i;//每次的查找，如果找K次还没找到，就不用找了
    			for(int j=i+1;i<len;j++)
    			{
    				if(arr[i] == arr[j])
    				{
    					count = count + 1;
    				}
    				else
    				{
    					k = k - 1;
    					if(k == 0)
    					{
    						break;
    					}
    				}
    				if(count>nums)
    				{
    					return arr[i];
    				}
    			}
    		}
    		return -1;
    	}