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]<kHeap[0]) {
kHeap[0]=arr[i];
heapify(kHeap,0,k);
}
}
return kHeap;
}
public static void heapInsert(int[] arr,int value,int index) {
arr[index] = value;
while(index !=0) {
int parent = (index -1)/2;
if(arr[parent]<arr[index]) {
swap(arr,parent,index);
index = parent;
}else {
break;
}
}
}
public static void heapify(int[] arr,int index,int heapSize) {
int left = index*2+1;
int right = index*2+2;
int largest = index;
while(left<heapSize) {
if(arr[left]>arr[index]) {
largest = left;
}
if(right<heapSize&&arr[right]>arr[largest]) {
largest = right;
}
if(largest!=index) {
swap(arr,largest,index);
}else {
break;
}
index = largest;
left = index*2+1;
right=index*2+2;
}
}
//O(N)
public static int[] getMinkNumsByBFPRT(int[] arr,int k) {
if(k<1||k>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]<minKth) {
res[index++]=arr[i];
}
}
for(;index!=res.length;index++) {
res[index]=minKth;
}
return res;
}
public static int getMinKthByBFPRT(int[] arr,int k) {
int[] copyArr = copyArray(arr);
return bfprt(copyArr,0,copyArr.length-1,k-1);
}
public static int[] copyArray(int[] arr) {
int[] res = new int[arr.length];
for(int i=0;i!=res.length;i++) {
res[i]=arr[i];
}
return res;
}
public static int bfprt(int[] arr,int begin,int end,int i) {
if(begin==end) {
return arr[begin];
}
int pivot = medianOfMedians(arr,begin,end);
int[] pivotRange = partion(arr,begin,end,pivot);
if(i>=pivotRange[0]&&i<=pivotRange[1]) {
return arr[i];
}else if(i<pivotRange[0]) {
return bfprt(arr,begin,pivotRange[0]-1,i);
}else {
return bfprt(arr,pivotRange[1]+1,end,i);
}
}
public static int medianOfMedians(int[] arr,int begin,int end) {
int num = end-begin +1;
int offset = num%5==0?0:1;
int[] mArr = new int[num/5+offset];
for(int i=0;i<mArr.length;i++) {
int beginI = begin +i*5;
int endI = beginI+4;
mArr[i]=getMedian(arr,beginI,Math.min(end, endI));
}
return bfprt(mArr,0,mArr.length-1,mArr.length/2);
}
public static int[] partion(int[] arr,int begin,int end,int pivotValue) {
int small = begin -1;
int cur = begin;
int big = end +1;
while(cur!=big) {
if(arr[cur]<pivotValue) {
swap(arr,++small,cur++);
}else if(arr[cur]>pivotValue) {
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<w) {
return null;
}
//java中LinkedList就是一个标准的双向链表，ArrayList是动态数组
LinkedList<Integer> qmax = new LinkedList<Integer>();
int[] res = new int[arr.length-w+1];
int index =0;
for(int i=0;i<arr.length;i++) {
while(!qmax.isEmpty()&&arr[qmax.peekLast()]<=arr[i]) {//双端队列尾部下标代表的值小于等于当前值
qmax.pollLast();//尾部弹出
}
qmax.addLast(i);
if(qmax.peekFirst()==i-w) {//如果窗口在初始时候没有形成完全，不会有任何一个下标弹出，当窗口形成之后，如果过期了从头部弹出一个下标
qmax.pollFirst();
}
if(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<Integer> qmin = new LinkedList<Integer>();
LinkedList<Integer> qmax = new LinkedList<Integer>();
int i=0;
int j =0;
int res=0;
while(i<arr.length) {
while(j<arr.length) {
while(!qmin.isEmpty()&&arr[qmin.peekLast()]>=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
