# Preface

This blog is completed step by step in the following order, which is also a learning process, so you can comment on any questions at any time. I hope we can make progress together.

# Stack, queue, heap

Stack, queue, heap data structure is not introduced, just need to know stack is first in first out, queue is first in first out. Here I will mainly introduce the heap, which is actually a binary tree. Let's go straight to the algorithm and implementation method.
1. Find the number K in an array
input:[2,3,4,5,6] k=2
output: 5

```#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
//Algorithmic thinking
//1. Create a priority queue with the size of K
//2. Maintain the priority queue. If the number is larger than the top of the priority queue, push the new element at the top of the pop until the end.
//3. The first K-large element is saved in the priority queue, and the first one is the K-large element
int Kmax(vector<int>&input,int k){
if(k>input.size())return 0;
std::priority_queue<int,vector<int>,greater<int>> max_queue;
int i;
for(i=0;i<k;++i){
max_queue.push(input[i]);
}
for(i=k;i<input.size();++i){
if(input[i]>max_queue.top()){
max_queue.pop();
max_queue.push(input[i]);
}
}
return max_queue.top();
}
```

2. Find the median in an array
input:[1,2,3] output:2
input:[1,2,3,4] output:2.5

```#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
namespace KMAX {
int Kmax(vector<int>&input,int k){
if(k>input.size())return 0;
std::priority_queue<int,vector<int>,greater<int>> max_queue;
int i;
for(i=0;i<k;++i){
max_queue.push(input[i]);
}
for(i=k;i<input.size();++i){
if(input[i]>max_queue.top()){
max_queue.pop();
max_queue.push(input[i]);
}
}
return max_queue.top();
}
//Get median
double getMidNum(vector<int>&input){
if(input.empty())return 0;
if(input.size()%2!=0){
return Kmax(input,input.size()/2+1);
}
else {
return (double)(Kmax(input,input.size()/2)+Kmax(input,input.size()/2+1))/2;
}
}
```

Combined with the idea of the first question, in fact, the median is the element with the largest K/2. If K is an odd number, it is directly k/2+1. For example, if K=3, it is the second one, that is, 3 / 2 + 1. Similarly, we can get the even number.
Minimum number of K: design an algorithm to find the minimum number of K in the array. You can return these K numbers in any order.

Example:

Input: arr = [1,3,5,7,2,4,6,8], k = 4
Output: [1,2,3,4]

```#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
vector<int> smallestK(vector<int>& input, int k) {
vector<int> output;
if(k>input.size()){return output;}
std::priority_queue<int,vector<int>,less<int>> min_queue;
int i;
for(i=0;i<k;++i){
min_queue.push(input[i]);
}
if(min_queue.empty())return output;

for(i=k;i<input.size();++i){
if(input[i]<min_queue.top()){
min_queue.pop();
min_queue.push(input[i]);
}
}
while(!min_queue.empty()){
output.push_back(min_queue.top());
min_queue.pop();
}
return output;
}
```

Given two sorted arrays A and B, the end of A has enough buffer space for B. Write A method to merge B into A and sort.

The number of elements initializing A and B are m and n, respectively.

Example:

Input:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

```//Reverse double pointer
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int pa = m - 1, pb = n - 1;
int tail = m + n - 1;
int cur;
while (pa >= 0 || pb >= 0) {
if (pa == -1)
cur = B[pb--];
else if (pb == -1)
cur = A[pa--];
else if (A[pa] > B[pb])
cur = A[pa--];
else
cur = B[pb--];
A[tail--] = cur;
}

}
```

# dynamic programming  Published 29 original articles, won praise 21, 10000 visitors+

Keywords: Programming less

Added by nigaki on Tue, 03 Mar 2020 10:06:45 +0200