747. Largest Number At Least Twice of Others

Problem

747. Largest Number At Least Twice of Others

https://leetcode.com/problems/largest-number-at-least-twice-of-others/description/

Intuition

Approach

어레이의 가장 큰 수가 다른 수들보다 2배 이상 큰지 확인하는 함수를 만들어야 한다. 클 경우 큰 수의 인덱스를, 그렇지 않을 경우 -1을 반환한다.

여기서 우리가 필요한 정보는

• 주어진 배열의 가장 큰 수의 인덱스
• 다른 수들과 비교했을 때 2배 이상 큰지

가장 큰 수는 반복문을 돌며 비교대조하는 방식으로 구하고 이때 큰 수의 값이 아닌 인덱스를 저장한다. 왜냐하면 그 위치를 기억해야하기 때문이다.

그 다음 주어진 배열로 돌아가서, 가장 큰 수와 같지 않은 수들, 즉 나머지 작은 수들과 비교를 하는데 그 작은 수들 중 하나라도 2배를 했을 때 큰 수보다 클 경우, -1를 반환한다. 그렇지 않은 경우에는 큰 수가 나머지 보다 2배 이상 큰 것임을 증명한 것이기 때문에 maxIndex를 최종 리턴하면 된다.

Complexity

• Time complexity:
  O(n**2)

• Space complexity:

Code

var dominantIndex = function(nums) {

  // To find the index of maximum number   
  let maxIndex = 0;

  for(let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[maxIndex]) {
      maxIndex = i;
    }
  }

  for(let j = 0; j < nums.length; j++) {
    if (nums[j] != nums[maxIndex]) {
      if (nums[j]*2 > nums[maxIndex]) {
        return -1;
      }
    }
  }
  return maxIndex;

};