[Array / String] Majority Element

169. Majority Element

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

1-1. Using two pointers

/**
 * @param {number[]} nums
 * @return {number} 
 */
var majorityElement = function(nums) {
  if(nums.length === 1) {
    return nums[0];
  }

  nums.sort((a, b) => a - b);

  let sp = 0;
  let ep = 0;
  let maxCnt = 0;
  let maxNum = 0;

  for(let i = 0; i < nums.length; i++) {       
    if(nums[i] === nums[i + 1]) {
      ep = i + 1;      
    } 
    else if(nums[i] !== nums[i + 1]) {            
      const cnt = ep - sp;

      if(maxCnt < cnt) {
        maxCnt = cnt;
        maxNum = nums[i - 1];        
      }

      sp = i;
    }                    
  }

  return maxNum;
};

Example 2를 예로

Input		: nums = [2,2,1,1,1,2,2]
Output		: 1
Expected 	: 2

루프를 거칠 때마다 sp(start point), ep(end point)은 다음과 같습니다.

sp = 0; ep = 1
sp = 0; ep = 2
sp = 0; ep = 2
sp = 3; ep = 4
sp = 3; ep = 5
sp = 3; ep = 6
sp = 3; ep = 6

두 포인터를 이용하여 maxNum을 찾고자 하였습니다.

1-2. Using n/2

/**
 * @param {number[]} nums
 * @return {number} 
 */
var majorityElement = function(nums) {
  if(nums.length === 1) {
    return nums[0];
  }

  nums.sort((a, b) => a - b);
  
  const midIdx = Math.floor(nums.length / 2);
  return nums[midIdx];
};

지문에 적힌 The majority element is the element that appears more than ⌊n / 2⌋ times. 를 참고하였습니다.

2. 해답을 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

Using counter variable

해답의 전문은 링크를 확인해주세요.

var majorityElement = function(nums) {
  let count = 0;
  let candidate = null;

  for(let num of nums) {
    if(count == 0) {
      candidate = num;
    }
    count += (num === candidate) ? 1 : -1;
  }

  return candidate;
};