[면접 문제] 맵 을 사용 하지 않 고 전체 수량의 절반 이 넘 는 숫자 를 구하 세 요.

1369 단어
전체 수의 배열 이 있 습 니 다. 주파수 가 전체 수량의 절반 을 초과 하 는 숫자 가 나타 나 기 를 구하 고 찾 지 못 하면 되 돌아 갑 니 다 - 1 예 를 들 어 [1, 2] = > - 1 [1, 1, 2, 3] = > - 1 (절반 을 넘 지 않 았 고 전체 4, 2 번 나 타 났 으 며 절반 을 넘 지 않 았 다) [2, 1, 2] = > 2 (전체 3, 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;
	}
문자열 의 역순 (자바 구현)
프로 그래 밍 인 스 턴 스 는 C \ # 의 BitmapData 를 사용 합 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage