선형 시간 내 에 T [0: n] 에 주 요소 가 있 는 지 확인 합 니 다.

3493 단어 시간.
T [0: n - 1] 을 설정 하면 n 개의 요소 의 배열 입 니 다.모든 요소 x 에 S (x) = {i | T [i] = x} 를 설정 합 니 다.| S (x) | > n / 2 일 때 x 를 T 의 주 요소 라 고 합 니 다.하나의 알고리즘 을 설계 하여 T [0: n - 1] 에 주 요소 가 있 는 지 확인 합 니 다.  
 
 
알고리즘 설명 은 다음 과 같 습 니 다.
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; }

좋은 웹페이지 즐겨찾기