배열에 k 번 발생하는 숫자가 있는지 확인하십시오.

Question

k 곱하기 발생하는 배열에 숫자가 존재하는지 확인하기 위해 나누기 및 정복 알고리즘 (O (nlgn) 런타임)을 만들고 싶습니다. 이 문제에 대한 제약 조건은 배열의 객체에 대해 평등/불균등 비교 메소드 만 정의된다는 것입니다 (즉, <,>을 사용할 수 없음).

그래서 나는 같은 크기 (대략)의 k 조각으로 배열을 분할하는 것을 포함하여 많은 접근법을 시도했다. 접근 방식은 배열에서 대다수 항목을 찾는 것과 비슷하지만 대다수의 경우 배열을 분할 할 때 대다수 항목이있는 경우 절반이 반드시 있어야한다는 것을 알 수 있습니다. 나를 올바른 방향으로 인도 할 수있는 조언이나 조언

EDIT : 배열을 반으로 나누고 재귀 적 솔루션을 사용하여 다수 항목을 찾는 문제가 k가 n/4 또는 n/4 일 수있는 다른 상황으로 확장 될 수 있는지 궁금합니다. 5 등

아마도 n/k를 사용하여 질문을 표현해야 할 것입니다.

Answer 1

이것은 불가능합니다. 이것이 불가능한 이유의 간단한 예로, length-n 배열, 모든 요소가 구별되며 k = 2 인 입력을 생각해보십시오. 요소가 두 번 나타나지 않는 유일한 방법은 모든 요소를 ​​O (n^2) 시간이 소요되는 다른 모든 요소와 비교하는 것입니다. 가능한 모든 비교를 수행 할 때까지 비교하지 않은 쌍이 실제로 같지 않은지 확신 할 수 없습니다.