LeetCode 703：数据流中的第 K 大元素

1、 LeetCode | 206.反转链表

2、 LeetCode | 24.两两交换链表中的节点

3、 LeetCode | 141.环形链表

4、 LeetCode | 20.有效的括号

5、 LeetCode | 225.用队列实现栈

6、 LeetCode | 232.用栈实现队列

这次来写一下 LeetCode 的第 703 题，数据流中的第 k 大元素。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

上面的题就是 数据流中的第K大元素 题目的截图，同时 LeetCode 给出了一个类的定义，然后要求实现 数据流中的第K大元素 的完整的算法。这次我同样没有使用 C 语言，而是使用了 C++ 语言，整个类的定义如下：

class KthLargest {

public:

    KthLargest(int k, vector& nums) {

    

    }




    int add(int val) {




    }

};




/**

 * Your KthLargest object will be instantiated and called as such:

 * KthLargest* obj = new KthLargest(k, nums);

 * int param_1 = obj->add(val);

 */

从上面的类定义可以看出，这次实现的是一个算法，也需要把题目给出的类的所有成员函数进行实现。

问题分析

这题的思路是先将给的数组进行排序，然后像数组添加元素时进行有序的插入，每次取倒数第 k 个元素即可。这次使用了 C++ 中的两个函数，分别是 sort 和 lower_bound，这两个函数的用法如下：

• sort 的使用方法
  对给定的数组进行排序，默认按照从小到大的方式进行排序
• lower_bound 的使用方法
  查找大于或等于 val 的第一个元素位置，如果所有元素都小于 val，则返回 last 的位置

代码实现

依据我的思路来写代码，代码还是比较简单的，代码如下：

class KthLargest {

private:

    vector m_nums;

    int m_k;

public:

    KthLargest(int k, vector& nums) {

        m_nums = nums;

        m_k = k;

        sort(m_nums.begin(), m_nums.end());

    }




    int add(int val) {

        m_nums.insert(lower_bound(m_nums.begin(), m_nums.end(), val), val);




        return m_nums[m_nums.size() - m_k];

    }

};




/**

 * Your KthLargest object will be instantiated and called as such:

 * KthLargest* obj = new KthLargest(k, nums);

 * int param_1 = obj->add(val);

 */

整个代码的逻辑并不复杂，进行简单的描述。

具体做法是在构造函数中将数组进行排序，在 add 函数插入元素的时候，找到元素应该插入的位置进行插入，保持数组的有序性。最后将数组中倒数第 k 个元素返回即可。

提交结果

在写完 KthLargest 类后，点击右下角的 “
执行代码
”，然后观察 
“输出” 和 “预期结果” 
是否一致，一致的话就点击 “
提交
” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，
如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，
如果没有通过，会给出失败的那一组测试用例，我们继续修改代码
。我们以上代码 “提交” 以后的截图如下：

上面的代码是我第一次能想到的代码，代码的执行时间太长了，可以优化的空间很大。如果有空我去优化了它，我再来分享吧。

喜欢就点在看哦~