[Java Script] 215. Kth Largest Element in an Array

1. 문제 개요

문제 링크 : 215. Kth Largest Element in an Array

Kth Largest Element in an Array - LeetCode

• 주어진 배열에서 k번째로 큰값의 인덱스를 반환하는 문제
• 주의사항 정렬을 사용하지않고 탐색해야한다

2. 문제 풀이

정렬을 사용하지않고 조회한다에서 우선 배열의 선형 탐색을 진행하는걸 기준으로 잡았습니다. 

이후 배열에서 가장 큰값을 찾아내고 해당값을 기준으로 순차적으로 값을 비교해가는 식으로 구현하였습니다.

 

LeetCode 요구 양식으로 코드 구현

var findKthLargest = function(nums, k) {
    let largest = -Infinity;
    
    for(let i=0;i<nums.length;i++){
        if(nums[i] > largest) largest = nums[i];
    }
    
    const hash = {};
    
    for(let i=0;i<nums.length;i++){
        const diff = largest-nums[i];
        hash[diff] = (hash[diff] || 0) + 1;
    }
    
    let count = 0;
    let diff = 0;
    while(count<k){
        count += (hash[diff] || 0);
        diff++;
    }
    
    return largest - diff + 1;
};

 

LeetCode 제출 결과

이렇게 구현에 성공하였습니다.

3. 시간 복잡도 계산

O(n) = O(n)

4. 개선 사항 및 어려웠던 점

정렬을 쓰지 않았기에 반복문을 여러번 사용해야 했고 이를 시간 복잡도를 높여야 했기에 이중 삼중 등의 반복문을 사용하지않고

개별로서 해결하게 구조를 짜는것이 가장 어려웠습니다.

5. 깃허브

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