[LeetCode/Easy] 703. Kth Largest Element in a Stream

목표: 입력된 수 중 k번째로 큰 수를 반환하는 클래스 구현

- 생성자

- int add(int val)

 

1. Input

1) 생성자: k, int[] nums

2) add(): val

- nums에 추가할 값

 

2. Output

1) add(): val을 추가한 후의 nums에서 k번째로 큰 값을 반환

 

3. Constraint

1) 1 <= k <= 104

2) 0 <= nums.length <= 10^4

3) - 10^4 <= nums[i] <= 10^4

4) - 10^4 <= val <= 10^4

5) add()는 최대 10^4번까지 호출된다.

6) 항상 k번째로 큰 값이 존재함을 보장한다.

 

4. Example

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); // [2,4,5,8]
kthLargest.add(3);   // [2,3,4,5,8], return 4
kthLargest.add(5);   // [2,3,4,5,5,8], return 5
kthLargest.add(10);  // [2,3,4,5,5,8,10], return 5
kthLargest.add(9);   // [2,3,4,5,5,8,9,10], return 8
kthLargest.add(4);   // [2,3,4,4,5,5,8,9,10], return 8

 

5. Code

1) 첫 코드(2023/05/30)

class KthLargest {
    List<Integer> list;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        list = new ArrayList<Integer>();
        for(int i : nums)
            list.add(i);
    }
    
    public int add(int val) {
        list.add(val);
        list.sort(Comparator.naturalOrder());
        return list.get(list.size()-k);
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

- 5%, 6%

 

2) 수정해본 코드(2023/05/30)

class KthLargest {
    List<Integer> list;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        list = new ArrayList<>();
        for(int i : nums)
            list.add(i);
        list.sort(Comparator.naturalOrder());
    }
    
    public int add(int val) {
        if(list.size()==0 || val<=list.get(0))
            list.add(0, val);
        else if(val>=list.get(list.size()-1))
            list.add(val);
        else
            for(int i=0 ; i<list.size()-1 ; i++)
                if(list.get(i)<=val && val<=list.get(i+1)){
                    list.add(i+1,val); break;
                }
        return list.get(list.size()-k);
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

- 7%, 10%