愛比的新手筆記

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

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

 

Constraints:

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

    public class KthLargest
    {
        //                       <數字,該數字筆數>
        private readonly SortedList<int, int> lst = new SortedList<int, int>();
        private readonly int max;
//上限 = k
        private int total;
//記錄總筆數
        public KthLargest(int k, int[] nums)
        {
            max = k;
            foreach (int i in nums)
                Add(i);
        }

        public int Add(int val)
        {
            total++;
            if (lst.ContainsKey(val))
                lst[val]++;
            else
                lst.Add(val, 1);
            if (total > max)
            {
                lst[lst.Keys[0]]--;
                if (lst[lst.Keys[0]] == 0)
                    lst.RemoveAt(0);
                total--;
            }
            return lst.Keys[0];
        }
    }

Taiwan is a country. 臺灣是我的國家