剑指offer 最小的k个数 、 leetcode 215. Kth Largest Element in an Array 、295. Find Median from Data Stream(剑指 数据流中位数)

时间:2021-07-30 20:37:18

注意multiset的一个bug:

multiset带一个参数的erase函数原型有两种。一是传递一个元素值,如上面例子代码中,这时候删除的是集合中所有值等于输入值的元素,并且返回删除的元素个数;另外一种是传递一个指向某个元素的iterator,这时候删除的就是这个对应的元素,无返回值。

https://www.cnblogs.com/lakeone/p/5600494.html

删除的时候一定不能删除指针,只能删除迭代器

leetcode那个题就是在这个地方出错的:

Input: [3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6] 20
Output: 3

Expected: 2

如果container.erase(*con),最后小根堆的大小就只有19个

container.erase(con)才是正确的

剑指offer 最小的k个数:

这是partition版本的

class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
int length = input.size();
if(input.empty() || length <= || k <= || length < k)
return result;
int start = ;
int end = length - ;
int index = partition(input,start,end);
while(index != k-){
if(index > k-){
end = index - ;
index = partition(input,start,end);
}
else{
start = index + ;
index = partition(input,start,end);
}
}
for(int i = ;i < k;i++)
result.push_back(input[i]);
return result;
}
int partition(vector<int> &input,int start,int end){
int small = start - ;
for(int i = start;i < end;i++){
if(input[i] < input[end]){
small++;
if(small != i)
swap(input,small,i);
}
}
small++;
swap(input,small,end);
return small;
}
void swap(vector<int>& input,int a,int b){
int tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}
};

这是基于大根堆的:

class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
int length = input.size();
if(input.empty() || k <= || length < k)
return output;
multiset<int,greater<int>> numbers;
multiset<int,greater<int>>::iterator greaternumber; vector<int>::iterator iter = input.begin();
for(;iter != input.end();iter++){
if(numbers.size() < k)
numbers.insert(*iter);
else{
greaternumber = numbers.begin();
if(*greaternumber > *iter){
numbers.erase(*greaternumber);
numbers.insert(*iter);
}
}
}
for(greaternumber = numbers.begin();greaternumber != numbers.end();greaternumber++){
output.push_back(*greaternumber);
}
return output;
}
};

leetcode 215. Kth Largest Element in an Array

使用小根堆

错误写法:

在这个情况:{3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6},会报错

错误在container.erase(*con),正确应该是container.erase(con)。erase(*con)删除的是数值,比如top是3,会把container里面所有的3都删除掉 ,erase(con)删除的是指针,只删除top的这个值

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int,less<int>> container;
multiset<int,less<int>>::iterator con; for(int i = ;i < nums.size();i++){
if(container.size() < k)
container.insert(nums[i]);
else{
con = container.begin();
if(*con < nums[i]){
container.erase(*con);
container.insert(nums[i]);
}
}
}
con = container.begin();
return *con;
}
};

正确写法:

可以写

if(length <= 0 || k <= 0 || length < k)
  return -1;

针对这个判断条件,有可能输入的不全是正数,返回-1就有问题,原题目中其实是排除了这些边界条件的

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int,less<int>> container;
multiset<int,less<int>>::iterator con;
//if(length <= 0 || k <= 0 || length < k)
//return -1;
for(int i = ;i < nums.size();i++){
if(container.size() < k)
container.insert(nums[i]);
else{
con = container.begin();
if(*con < nums[i]){
container.erase(con);
container.insert(nums[i]);
}
}
}
con = container.begin();
return *con;
}
};

使用partition的方式:

注意这里要增加end = index - 1和start = index + 1,因为这里不是递归,是使用的循环。如果你直接把end换成index - 1带入patition函数,对于之后的partition函数,这个end实际上还是没变的。

没有真正达到所以1/2的目的。

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
k = n - k;
int start = ,end = nums.size() - ;
int index = partition(nums,start,end);
int freq = ;
while(index != k){
if(index > k){
end = index - ;
index = partition(nums,start,end);
}
else{
start = index + ;
index = partition(nums,start,end);
}
}
return nums[index];
}
int partition(vector<int>& nums,int start,int end){
int index = start - ;
for(int i = start;i < end;i++){
if(nums[i] < nums[end]){
index++;
if(index != i)
swap(nums[index],nums[i]);
}
}
index++;
swap(nums[index],nums[end]);
return index;
}
};

80. Median

这个题是在无序数组中找经过排序后的中间位置的值。实际上这个题和Kth Largest Element in an Array差不多,Kth Largest Element in an Array是求第k大,这个题是限定了k是中间位置,并且要求时间复杂度是O(n),所以使用partition的方式就可以。

时间复杂度分析:

https://rcoh.me/posts/linear-time-median-finding/

这是平局时间复杂度

实际上就是O(N) + O(N/2) + O(N/4) + O(N/8)....,使用等比数列求和公式:

剑指offer 最小的k个数 、 leetcode 215. Kth Largest Element in an Array 、295. Find Median from Data Stream(剑指 数据流中位数)

就可以得到是一个O(2N)的复杂度,即O(N)

class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer denotes the middle number of the array
*/
int median(vector<int> &nums) {
// write your code here
int start = ,end = nums.size() - ;
int index = partition(nums,start,end);
int k = (nums.size() - )/;
while(k != index){
if(index < k){
start = index + ;
index = partition(nums,start,end);
}
else{
end = index - ;
index = partition(nums,start,end);
}
}
return nums[index];
}
int partition(vector<int>& nums,int start,int end){
int index = start - ;
for(int i = start;i < end;i++){
if(nums[i] < nums[end]){
index++;
if(i != index)
swap(nums[i],nums[index]);
}
}
index++;
swap(nums[end],nums[index]);
return index;
}
};

295. Find Median from Data Stream

使用两个堆进行存储,一个是大根堆,即存储所有较小的数;一个是小根堆,即存储所有较大的数。使用priority_queue来代表大小根堆。

class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() { } void addNum(int num) {
if(p.size() == || p.top() > num)
p.push(num);
else
q.push(num);
if(p.size() > q.size() + ){
int tmp = p.top();
p.pop();
q.push(tmp);
}
if(q.size() > p.size()){
int tmp = q.top();
q.pop();
p.push(tmp);
}
} double findMedian() {
return p.size() > q.size() ? p.top() * 1.0 : (p.top() + q.top())/2.0;
}
priority_queue<int,vector<int>,less<int>> p;
priority_queue<int,vector<int>,greater<int>> q;
};