[Java Script]LeetCode 169. Majority Element

1. 문제 개요

문제 링크 :  169. Majority Element

 

• 주어지는 배열에서 중복값이 가장 많은 원자값을 찾아내시오

2. 문제 풀이

배열의 원자값중 중복값이 가장많은 값을 고르는 방식이기에 80번 문제에서 사용한것과 동일한 방식을 이용하여

선 정렬후 배열 탐색 과정에서 전후값을 비교하여 개수를 체크하는 방식으로 풀어보겠습니다

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같은데

var majorityElement = function(nums) {
	// 탐색할 필요하 겂는경우 체크(배열의 길이가 1)
	// 주어진 배열값 정렬
 	// 전후값을 비교하여 중복값을 카운팅 하는 반복문 구현   
    // 최대 중복값 카운트 값 반환
};

 

LeetCode 요구 양식으로 코드 구현

 

var majorityElement = function(nums) {
    if(nums.length == 1) return nums[0]
    nums.sort(function (a, b) { return a - b });
    let before, max, maxCount = 0, count = 0;
    for(i=0; i < nums.length; i ++){
            if(before == nums[i]){
                count++
                if (count > maxCount) {
                    max = nums[i]                
                    maxCount = count    
                }
            }
            else count = 0;
            before = nums[i]
    }
    return max
};

 

LeetCode 제출 결과

 

 

3. 시간 복잡도 계산

node 의 sort 함수의 경우 카운팅 정렬을 사용하기에 시간복잡도가 O(n) 입니다.

O(n) + O(n) = O(2n) => O(n) 

 

4. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.