题目一：求前m大的数
?
?
?代码解答：
package 第八天分治思想;
import java.util.Arrays;
public class 输出前m大的数 {
static void arrangRight(int []a,int s,int e,int k ){
int i=s;
int j=e;
//int m=s+(e-s)/2;
int key=a[i];
if(e>=s){
return ;
}
while(i!=j) {
while (i < j && a[j] >= key) {
j--;
}
a[i] = a[j];
while (i < j && a[i] <= key) {
i++;
}
a[j] = a[i];
}
a[i]=key;
if((s-i+1)==k){
return;
}
else if((s-i+1)>k){
arrangRight(a,i+1,e,k);
}
else arrangRight(a,s,i-1,k-(s-i+1));
}
public static void main(String[] args) {
int []a=new int[5];
a[0]=0;
a[1]=1;
a[2]=2;
a[3]=3;
a[4]=4;
int []b=new int[5];
arrangRight(a,0,a.length-1,3);
Arrays.sort(a,2,4);
for (int i=2;i<5;i++){
System.out.println(a[i]);
}
}
}
题目二：求排列的逆序数
?
?代码解答：
package 第八天分治思想;
import java.util.Arrays;
import java.util.Scanner;
//
public class 求排列的逆序数 {
static int [] a=new int[6];
static int [] b=new int[6];
static int ans=0;
static void paixu(int s,int e){
if(s<e){//为什么要用if，而不能用while
int m=s+(e-s)/2;
paixu(s,m);
paixu(m+1,e);
paixu1(s,e);
}
}
static void paixu1(int s,int e){//此函数的作用为将数组a里面的[a,m],[m+1],e段进行排序
int p0=0;//作为新数组的指针
int p1=s;
int m=s+(e-s)/2;
int p2=m+1;//两个数组开头的指针
while(p1<=m&&p2<=e){
if(a[p1]<a[p2]){
b[p0++]=a[p2++];
}else {
b[p0++]=a[p1++];
ans += e - p2 + 1;//这也太帅了吧，我悟了
}
}
while(p1<=m){
b[p0++]=a[p1++];
}
while(p2<=e){
b[p0++]=a[p2++];
}
for(int i=0;i<e-s+1;i++){
a[s+i]=b[i];
}
}
public static void main(String[] args) {
// int [] a=new int[6];
// int [] b=new int[6];
a[0]=2;
a[1]=6;
a[2]=3;
a[3]=4;
a[4]=5;
a[5]=1;
//排序算法
paixu(0,5);
// for(int i:b){
// System.out.println(i);
// }
System.out.println(ans);
}
}
//写代码就跟在梦一样
//笑死
谁能想到只改动这么一点点呢，很强