703. Kth Largest Element in a Stream

Kth Largest Element in a Stream - LeetCode

Kth Largest Element in a Stream - LeetCode

 

주어지는 배열에서 "k" 번째로 큰 수를 찾는 문제입니다.

 

큰 수라는 내용에서 알 수 있듯이 결국 주어진 수에서 값을 찾기 위해서는 정렬이 필요합니다.

 

가장 쉽게 접근하기 위해서는 주어진 ( 입력된 ) 배열을 정렬 ( 내림차순 ) 하고 k 번째 index 를 찾으면 됩니다.

이를 위해서는 sort 와 arr[k] ( indexer ) 가 필요합니다.

 

/**
 * @param {number} k
 * @param {number[]} nums
 */

var KthLargest = function(k, nums) {
    this.k = k;
    this.nums = nums;
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.nums.push(val);
    this.nums.sort((a, b) => a - b);

    return this.nums[this.nums.length - this.k];
};

요렇게 접근하면 문제를 해결할 수 있습니다. 다만, 런타임 실행 비용이 조금 크게 나옵니다.

 

개선할 수 있는 수단은 여러가지가 있지만 대표적으로 k 번째 입력 값으로부터 작은 값은 버리고
입력 값보다 큰 수는 따로 관리되는 자료형에 저장한 다음 k 번째 입력 값을 갱신하면 됩니다.

 

예로 Queue 를 사용하는 방법이 있지만 비슷한 방법으로 접근한 코드는 아래와 같습니다.
( 접근 방법은 유사 합니다 )

 

function push(arr, k, val) {
    // not full of arr by 'k' bucket.
    // fill val by ascending order.
    if (arr.length < k) {
        var idx = 0;
        while (arr[idx] < val) {
            idx++;
        }
        arr.splice(idx, 0, val);
    } else {
        // throw value when smaller than arr[0] ( = index by k )
        if (arr[0] < val) {
            for (var i = 0; i < arr.length; i++) {
                // when last index, set val at last.
                if (i + 1 == arr.length) {
                    arr[i] = val;
                } else {
                    // check between val and 'next'.
                    // next is bigger than val, set val at current index.
                    if (val < arr[i + 1]) {
                        arr[i] = val;
                        break;
                    } else {
                        // shift left
                        // * we must set 'val' at this arr and arr size is small
                        arr[i] = arr[i + 1];
                    }
                }
            }
        }
    }
}

/**
 * @param {number} k
 * @param {number[]} nums
 */

var KthLargest = function (k, nums) {
    this.k = k;
    this.candidates = new Array();

    nums.forEach(num => push(this.candidates, this.k, num));
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
    push(this.candidates, this.k, val);
    
    return this.candidates[0];
};

정렬 및 삽입을 흉내내고 있습니다. 이러면 O ( N ) 의 런타임 실행 비용이 발생합니다.
* 초기화 ( splice ) 도 조금 더 개선할 수 있습니다