LeetCode169. Majority Element C 언어

1282 단어
Given an array of size n, find the majority element. The majority element is the element that appears more than  n/2  times.
You may assume that the array is non-empty and the majority element always exist in the array.

제목: 그룹 중 절반이 넘는 수를 찾습니다.이 문제는 Majority Element이 반드시 존재한다고 가정합니다.안 그러면 존재하지 않는다고 판단해야 돼. 어떡해?
int majorityElement(int* nums, int numsSize) {
    //           
    // int size=0;
    // if(numsSize%2==0){
    //     size=numsSize/2;
    // }else{
    //     size=(numsSize-1)/2;
    // }
    // int i,j;
    // int count=0;
    // int flag=0;
    // for(i=0;isize){
    //         flag=i;
    //         break;
    //     }
    //     }else{
    //         break;
    //     }
    // }
    // return nums[i];    
    //        Moore‘S voting Algorithem
    //   http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
    //            
    int candidate;
    int count=0;
    for(int i=0;i

PS:원래 멍청해서 두 겹으로 순환해서 만들었어요.시간의 복잡도는 관문을 통과하지 못한다.
그리고 인터넷에서 찾아보니 Moore's voting Algorithem 알고리즘이 발견됐어요. 이런 문제를 전문적으로 해결하는 알고리즘도 있고 알고리즘 설명도 있어요.http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
복!
전재 대상:https://blog.51cto.com/fulin0532/1867859

좋은 웹페이지 즐겨찾기