Answers
首先要用快速排序数组按从小到大的顺序排序，然后用两分法，按照如下的数组元素和
下标之间的关系进行快速查找。
记：D= 当前数组元素值 - 当前数组元素下标 - 1
D=0，说明当前数组元素的左边包括当前元素没有被移除的数值
D=1，说明当前数组元素的左边包括当前元素有1个被移除的数值
D=2，说明当前数组元素的左边包括当前元素有2个被移除的数值
D=3，说明当前数组元素的左边包括当前元素有3个被移除的数值
根据以上思路，可以用递归方式完成查找，java函数如下：
//函数find寻找整数数组a中在区间[b,e]中被移除的c个数字，结果被打印到屏幕
void find（int[] a, int b, int e, int c){
if(c==0) return;
if(e==b+1){
if(c == 2){
System.out.println(a[b]);
System.out.println(a[e]);
}else{
if(a[e]==a[b])
System.out.println(a[b]);
else
System.out.println(a[e]);
}
return;
}
int m = (b + e)>>1;
int dm = a[m] - m - 1;
int db = a[b] - b - 1;
int d = dm - db;
if(d > 0){
find(a, b, m, d);
}
if(c>d){
find(a, m + 1, e, c-d);
}
}
Lrmax
answered 12 years, 1 month ago