703. 数据流中的第 K 大元素
难度简单227 收藏 分享 切换为英文 接收动态 反馈
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
-
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。 -
int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
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
官方解法（使用优先级队列）:
class KthLargest {
private PriorityQueue<Integer> queue;
private int k;
public KthLargest(int k, int[] nums) {
queue=new PriorityQueue<>();
this.k=k;
for(int num:nums){
add(num);
}
}
public int add(int val) {
if(queue.size()<k){
queue.offer(val);
}else if(queue.peek()<val){
queue.poll();
queue.offer(val);
}
return queue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
119. 杨辉三角 II
难度简单223 收藏 分享 切换为英文 接收动态 反馈
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 *k *行。
image
在杨辉三角中，每个数是它左上方和右上方的数的和.
示例:
输入: 3
输出: [1,3,3,1]
解法1（递归求解）:
class Solution {
public List<Integer> getRow(int rowIndex) {
//递归解法
List<List<Integer>> list=new ArrayList<>();
for(int i=0;i<=rowIndex;i++){
List<Integer> row=new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0||j==i){
row.add(1);
}else{
row.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
}
}
list.add(row);
}
return list.get(rowIndex);
}
}
优化：由于每一次都只用到了上一层的数据，所以只要保存上一层的数据就够了。这样在空间复杂度上可以提升一点。
class Solution {
public List<Integer> getRow(int rowIndex) {
//递归解法
List<Integer> pre=new ArrayList<>();
for(int i=0;i<=rowIndex;i++){
List<Integer> cur=new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0||j==i){
cur.add(1);
}else{
cur.add(pre.get(j-1)+pre.get(j));
}
}
pre=cur;
}
return pre;
}
}
再优化以下：
class Solution {
public List<Integer> getRow(int rowIndex) {
//递归解法
List<Integer> row=new ArrayList<>();
row.add(1);
for(int i=1;i<=rowIndex;i++){
row.add(0);
for(int j=i;j>0;j--){
row.set(j,row.get(j)+row.get(j-1));
}
}
return row;
}
}
