이 일반적인 질문을 약간 비틀어 해결하는 데 문제가 있습니다.
내부에 숨겨진 숫자 하나가있는 n 개의 상자와 두 개의 상자에 동일한 또는 다른 숫자가 포함되어 있는지를 결정하는 테스트 절차가 주어지면 대부분의 상자에있는 숫자가 있는지 확인합니다. 즉, n 개 이상의 숫자가 있는지 확인합니다. O (n log n) 시간에 동일한 숨겨진 숫자를 가진 / 2 상자.
나는 Moore의 투표 알고리즘을 알고 있지만이 문제는 약간 다른 것 같습니다.
Moore의 투표 알고리즘을 그대로 사용할 수 있습니다 (O (n) 시간 및 O (1) 공간에서 수행됨).
시작 위치에서 시퀀스를 스윕합니다.
우리는 현재 후보와 카운터로 구성된 쌍을 유지합니다. 처음에는 현재 후보를 알 수 없으며 카운터는 0입니다.
포인터를 요소 위로 앞으로 이동하면
e:
- 카운터가 0이면 현재 후보를로
e설정하고 카운터를 1로 설정합니다.- 카운터가 0이 아니면
e현재 후보 인지 여부에 따라 카운터를 늘리거나 줄 입니다.완료되면 현재 후보가 다수 인 경우 다수 요소입니다.
어떤 상황에서는 다수의 요소가 있음을 알고 있거나 가정합니다.
그러나 선택한 요소가 실제로 주요 요소인지 확인해야하는 경우 데이터를 한 번 더 선형 전달하여 수행해야합니다.
이 알고리즘은 현재 후보가 일치하는지 확인하는 것만 포함 e하므로 동등성 확인만으로 충분합니다.
최종 후보가 과반수 요소인지 확인하려면 각 요소를 후보와 비교하고 일치 수를 세는 또 다른 통과를 수행하면됩니다. 일치 수가 n / 2보다 크면 실제로 대부분의 요소를 찾은 것입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다