선형 시간 내 에 T [0: n] 에 주 요소 가 있 는 지 확인 합 니 다.
3493 단어 시간.
알고리즘 설명 은 다음 과 같 습 니 다.
a1 a2 a3 a4... aj aj + 1... an 은 먼저 a1 을 가 져 와 m 에 저장 하고 카운터 k 를 1 로 설정 합 니 다.
그리고 m 로 하여 금 a1, a2 를 비교 하 게 하고 m 와 같 으 면 k 에 1 을 더 하고 다 르 면 k 는 1 을 빼 야 한다.
이렇게 실행 하면 aj 를 비교 할 때 k = 0 일 수 있 습 니 다. 이때 aj + 1 을 새로 가 져 와 m, k 를 1 로 저장 합 니 다.
상기 조작 을 반복 하면 a [1: n] 의 모든 요 소 를 비교 한 것 을 알 수 있 습 니 다.
이 과정 이 끝 난 후에 k 는 두 가지 가능 한 값 이 있 습 니 다. ① k = 0, ② k > 0.
k = 0 시 a [0: n - 1] 는 주 원소 가 없습니다.
k > 0 시 a [0: n - 1] 는 주 원소 가 있 을 수도 있 고 주 원소 가 없 을 수도 있 습 니 다.만약 a [0: n - 1] 에 주 원소 가 있다 면 m 의 값 은 반드시 주 원소 가 되 어야 한다.분명히 m 와 a [0: n - 1] 의 모든 요 소 를 다시 한 번 비교 하면 m 가 a [0: n - 1] 의 주요 요소 인지, 즉 a [0: n - 1] 에 주요 요소 가 있 는 지 알 수 있다.
알고리즘 은 다음 과 같 습 니 다.
Template<class T>
void MainMember(T a[],int n)
{
int i,j,k,m;
m=a[0];k=1;j=0;
for(i=1;i<n;i++)
{
if(m==a[i]) k++;
else k--;
if(k==0)
{
i++;
if(i>n) break;//a[0:n-1] ,
m=[i];
k=1;
}
}
if(k==0)
cout<<" a !"<<endl;
else
{
for(i=0;i<n;i++)
if(m==a[i]) j++;
}
if(j>n/2)
cout<<" a , :"<<m<<endl;
else cout<<" a !"<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 는 2018 - 11 - 07T 11: 40: 13.202518781 + 08 을 시간 형식 으로 변환 합 니 다.오류 메시지java.text.ParseException: Unparseable date: "2018-11-07T11:40:13.202518781+08:00" 배경 제3자 플랫폼 데 이 터 를 연결 하여 전 달 된 시...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.