출현 횟수가 절반(50%)을 넘는 수

[제목 요구] n개수와 n을 드리겠습니다.지금 당신이 O(n)의 시간 내에 O(1)의 공간에서 출현 횟수가 50%를 넘는 수를 찾아내야 합니다.
[허튼소리 시작] 처음에 나는 이 문제를 보고 순간적으로 (ToT)/~~(.n.*), O(n)의 시간이라는 한 가지 요구만 있으면 해시로 순간적으로 해결할 수 있다(즉 공간으로 시간을 바꾸는 것), O(1)의 공간에 대해서는 해결하기 어려울 것 같다.
[사고방식1] 이중 순환, 이것은 이 문제를 해결하는 효율이 가장 낮은 방법이다. 즉, 모든 수에 대해 그것이 나타난 횟수를 계산하고 시간 복잡도 O(n^2)를 직접 출력하는 것이다.
[사고방식2] 먼저 순서를 정하고 비슷한 숫자를 한데 배열한 다음에 첫 번째 수부터 훑어본다. 지금 예를 들어 1000012, 지금 순서를 정한다. 0000112, 0부터 계수기 T=0을 설정하고 현재 4개의 0이 있으면 T=4를 한다. 반수를 초과하고 0을 출력하는 것을 발견했다.이 방법은 바로 이전 방법의 최적화판, 아웃이다.
[사고방식 3]은 바로 공간으로 시간을 바꾸는 것이다. 해시의 사상은 1차원 수조에 두 가지 의미를 가진다.예를 들어 a[x]=y는 x라는 숫자에 y번이 나타난다. 이 방법의 시간 복잡도는 O(n)이지만 공간은 정말...말하지 않는다(*￣洌)Out
[사고방식4] 먼저 확률을 계산하고 이 수 중에서 요구에 가장 부합될 수 있는 몇 개의 수를 선택한 다음에 무작위로 몇 개를 추출한다.이..그냥 넘어가자.
[사고방식 5] 오늘의 주제는 이른바 MJRTY 알고리즘이고 다수의 투표 알고리즘이라고도 부른다. 주요 사고방식은 다음과 같다. (이 알고리즘의 시간 복잡도 O(n)!공간에 별도의 저장이 필요하지 않기 때문에 공간의 복잡도는 O(1)!!!!!!)
만약count==0이면vote의 값을 수조의 현재 요소로 설정하고count의 값을 1로 부여합니다.
그렇지 않으면vote와 현재 그룹 원소의 값이 같으면count++, 반대로countC;
수조를 스캔할 때까지 상기 두 단계를 반복합니다.
count 값은 0입니다. 다시 처음부터 그룹을 스캔합니다. 그룹 요소 값이vote 값과 같으면count++로 그룹을 스캔할 때까지 합니다.
만약에 이때count의 값이 n/2보다 크면vote의 값을 되돌려주고 반대로는-1을 되돌려줍니다.
다음은 코드 구현입니다. 문제 보증 결과가 반드시 존재하기 때문에 우리는 마지막 검사 검증을 생략했습니다.
주요 코드는 다음과 같습니다.

#include<iostream>
using namespace std;
int len; 
void Find(int* a, int N) 
{
char candidate;
int nTimes, i;
for(i=nTimes=0;i<N;i++)
{
if(nTimes==0) candidate=a[i],nTimes=1;
else
{
if(candidate==a[i]) nTimes++;
else nTimes--;
}
}
cout<<candidate; 
}
int main()
{
cin>>len;
int a[len];
for(int i=0;i<n;i++) cin>>a[i];
Find(a,len);
system("pause");
return 0;
} 

위에서 말한 것은 편집자가 여러분께 소개한 출현 횟수가 절반(50%)이 넘는 숫자입니다. 여러분께 도움이 되었으면 합니다. 궁금한 점이 있으면 저에게 메시지를 남겨 주십시오. 편집자는 제때에 답장을 드리겠습니다.여기에서도 저희 사이트에 대한 지지에 감사드립니다!