BFPRT算法：
int bfprt(arr,k){
//1.分组
//2.组内排序
//3.中位拿出组成N/5大小的新数组 new_arr[]
//4.num = bfprt(new_arr,new_arr.length/2)
//5.原数组根据num做划分，小于num的放在左边，等于num的放在中间，大于num的放在右边，最后看是否命中k,命中了直接返回，没有命中，选一侧走}
文章图片
Image 2.png
文章图片
Image 3.png
文章图片
Image 4.png
文章图片
Image 5.png
文章图片
Image 6.png
package com.znst;
public class Demo {//o(N*longk)用堆做的，不是bfprt算法
public static int[] getMinkNumsByHeap(int[] arr,int k) {
if(k<1||k>arr.length) {
return arr;
}
int[] kHeap = new int[k];
for(int i=0;
i!=k;
i++) {
heapInsert(kHeap,arr[i],i);
}
for(int i=k;
i!=arr.length;
i++) {
if(arr[i]arr.length) {
return arr;
}
int minKth = getMinKthByBFPRT(arr,k);
int[] res = new int[k];
int index =0;
for(int i =0;
i!=arr.length;
i++) {
if(arr[i]=pivotRange[0]&&i<=pivotRange[1]) {
return arr[i];
}else if(ipivotValue) {
swap(arr,cur,--big);
}else {
cur++;
}
}
int[] range =new int[2];
range[0]=small+1;
range[1]=big-1;
return range;
}public static int getMedian(int[] arr,int begin,int end) {
insertionSort(arr,begin,end);
int sum = end+begin;
int mid = (sum/2)+(sum%2);
return arr[mid];
}public static void insertionSort(int[] arr,int begin,int end) {
for(int i=begin+1;
i!=end+1;
i++) {
for(int j=i;
j!=begin;
j--) {
if(arr[j-1]>arr[j]) {
swap(arr,j-1,j);
}else {
break;
}
}
}
}public static void swap(int[] arr,int index1,int index2) {if(arr!=null) {
int temp = arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
}
public static void printArray(int[] arr) {
for(int i =0;
i!=arr.length;
i++) {
System.out.println(arr[i]+" ");
}
System.out.println();
}public static void main(String[] args) {
int[] arr = {6,9,1,3,1,2,2,5,6,1,3,5,9,7,2,5,6,1,9};
printArray(getMinkNumsByHeap(arr,10));
printArray(getMinkNumsByBFPRT(arr,10));
}
} 介绍窗口以及窗口内最大值或最小值的更新结构（单调双向队列）
文章图片
Image 8.png
package com.znst;
import java.util.LinkedList;
public class Demo2 {public static int[] getMaxWindow(int[] arr,int w) {
if(arr==null||w<1||arr.length qmax = new LinkedList();
int[] res = new int[arr.length-w+1];
int index =0;
for(int i=0;
i=w-1) {//收集最大值，返回
res[index++]=arr[qmax.peekFirst()];
}
}
return res;
}} 
文章图片
Image 9.png
package com.znst;
import java.util.LinkedList;
public class Demo2 {public static int getNum(int[] arr,int num) {
if(arr==null||arr.length==0) {
return 0;
}
LinkedList qmin = new LinkedList();
LinkedList qmax = new LinkedList();
int i=0;
int j =0;
int res=0;
while(i=arr[j]) {
qmin.pollLast();
}
qmin.addLast(j);
while(!qmax.isEmpty()&&arr[qmax.peekLast()]<=arr[j]) {
qmax.pollLast();
}
qmax.addLast(j);
if(arr[qmax.getFirst()]-arr[qmin.getFirst()]>num) {
break;
}
j++;
}
if(qmin.peekFirst()==i) {
qmin.pollFirst();
}
if(qmax.peekFirst()==L) {
qmax.pollFirst();
}
res+=j-i;
i++;
}
return res;
}} 【算法进阶二】介绍单调栈结构
文章图片
Image 10.png
文章图片
Image 11.png
文章图片
Image 12.png
文章图片
Image 13.png
