[면접 문제] 이미 알 고 있 는 비율, 배열 에 많이 나 오 는 요 소 를 찾 아 라.

문 제 는 프로 그래 밍 의 아름다움 에서 발췌 한 것 이다.
문제 1: 무질서 한 배열 에서 특정한 요소 A 의 출현 횟수 가 총수 의 1 / 2 보다 많 습 니 다. 어떻게 찾 습 니까?
문제 2: 하나의 무질서 한 배열 에서 만약 에 세 개의 요소 가 A, B, C 의 출현 횟수 가 모두 총수 의 1 / 4 보다 많 으 면 어떻게 그것들 을 찾 습 니까?
 
정 답 1:
a > 배열 정렬, O (nlogn), 그리고 정렬 된 배열, O (n) 를 옮 겨 다 니 며 가장 긴 같은 서열 을 찾 습 니 다.(이것 은 통용 적 인 해법 이지 만 A 의 등장 이 1 / 2 이상 이기 때문에 에서 배열 의 중위 수 를 직접 취하 면 된다 고 말 했다.)어쨌든 전체적으로 O (nlogn) 입 니 다.
b > 배열 요소 순 서 를 hash 표 에 삽입 합 니 다. key 가 존재 하지 않 으 면 val = 1;키 가 존재 할 때, val + = 1;O(n)
모두 삽입 한 후 hash 표 에서 val 이 가장 큰 것 을 통계 하면 됩 니 다.단점 은 hash 표를 사용 해 야 한 다 는 것 입 니 다. 공간 복잡 도가 높 고 hash 표 에서 원 배열 요 소 를 옮 겨 다 니 며 O (n) 임 을 보증 할 수 있 습 니 다.
c > 우 리 는 매번 배열 에서 두 개의 서로 다른 요 소 를 꺼 내 면 두 가지 상황 (1, 이 두 가지 요 소 는 A, 2, 그 중의 한 요 소 는 A) 이 있 을 수 있다 는 것 을 발견 했다. 어떤 상황 이 든 배열 의 나머지 요소 중 A 의 출현 횟수 가 1 / 2 보다 많 기 때문에 반복 적 으로 가 져 가면 마지막 에 남 은 것 은 반드시 A 이다.코드 는 다음 과 같 습 니 다:

int FindMajority( int* arr, int count )
{
	int ret = arr[0];
	int rep = 1;
	for( int i = 1; i < count; ++i )
	{
		if( ret == arr[i] ) ++rep;
		else if( --rep == 0 ) ret = arr[i+1];  //        i+1     ，                count/2
	}
	return ret;
}

 
정 답 2:
답 1 의 세 번 째 방법 과 비슷 하 다. 매번 배열 에서 4 개의 서로 다른 요 소 를 꺼 내 면 A, B, C 가 이 4 개의 서로 다른 요소 에서 최대 1 번 까지 나타 나 고 나머지 요소 에서 1 / 4 이상 의 비례 를 확보 할 수 있다.마지막 으로 남 은 세 가지 요소 가 결과 다.코드 는 다음 과 같 습 니 다:

//    3    ，            ，         
int FindMajority3( int* arr, int count, int& A, int& B, int& C ) 
{
    int repA = 0, repB = 0, repC = 0;
    A = -1;  //           ，        
    B = -2; 
    C = -3; 
    for( int i = 0; i < count; ++i )
    {   
        if( arr[i] == A || repA == 0 ) A = arr[i], ++repA;
        else if( arr[i] == B || repB == 0 ) B = arr[i], ++repB;
        else if( arr[i] == C || repC == 0 ) C = arr[i], ++repC;
        else --repA, --repB, --repC;
    }   
}

 
요약:
이 를 통 해 알 수 있 듯 이 이런 문제 에 부 딪 히 면 매번 에 일부 요 소 를 추출 하고 원 소 를 추출 한 후에 나머지 는 원래 의 비례 를 유지 할 수 있다. 그러면 문제 의 규 모 를 줄 일 수 있다. 또한 이런 방법 은 O (n) 시간 이 복잡 해서 대체적으로 가장 좋 은 해법 이 라 고 할 수 있다.
자, 누가 물 어보 면 무질서 한 배열 에서 발생 하 는 횟수 가 총수 의 2 / 5 보다 많 습 니 다. 이 수 를 찾 으 면 하 시 겠 습 니까?