这更像是一个自定义的编程练习,而不是一个真正的问题。我有一系列java.lang.Comparable
项目。我需要维护两个指针(数组的索引,即 int 值) i,j 。i 从数组的开头开始向右移动,直到遇到小于或等于前一个元素的元素。当它这样做时,它停止向右移动并最终指向乱序的元素(不大于前一个的元素)。类似地,j 从数组的末尾开始向左移动,直到找到一个不小于前一个的元素。
另外,我需要确保索引不会用完数组,即我不能低于 0 并且 j 不能高于 arraylength-1
假设我们有一个包含 5 个元素的数组。
i = 0;
j = 4;(which is the arraylength-1 )
if C,D,E,F,G is the array ,the final values of i and j will be
i = 4 and j = 0
if array is J,D,E,F,G ,the final values of i, j will be
i = 0 , j = 0
if array is B,C,A,D,G , final values of i,j will be
i = 2 , j = 1
我尝试将逻辑编码for moving i to the right, using a while loop
如下。在两种情况下,我能够让它为 i 指针工作。
public class PointerMovement{
public static void ptrsPointToOutOfOrderElements(Comparable[] a){
int lo = 0;
int hi = a.length-1;
int i = lo;
int t=i+1;
int j = hi;
//only for moving i to the right .
while(less(a[i],a[t])){
if(t == hi){
i=t;
break;
}
i++;
t++;
}
i=t;
for(Comparable x:a){
System.out.print(x+",");
}
System.out.println();
System.out.println("bad element or end of array at i="+i+"==>"+a[i]);
}
private static boolean less(Comparable x,Comparable y){
return x.compareTo(y) < 0;
}
public static void main(String[] args) {
String[] a = new String[]{"C","D","E","F","G"};//works
//String[] a = new String[]{"B","C","A","D","G"};//works
//String[] a = new String[]{"J","D","E","F","G"};//fails!
ptrsPointToOutOfOrderElements(a);
}
}
我的推理如下
我维护i=0;
和另一个变量t=i+1
当 while 循环失败时,less(a[i],a[t])
为 false。我们需要返回一个指向 a[t] 的指针,它是无序的。所以 i=t 并返回 i。
如果我们到达数组的右端,则测试 if(t == hi) 通过并且我们分配 i=t 并且现在 i 指向数组的末尾。
但是,当乱序元素位于数组中的第 0 位时,代码会失败。
J,D,E,F,G
我们得到 i=1 而不是 i (=0) 因为 i=t 是分配的。i 最终指向 D 而不是 J。
有人可以指出我正确的方向吗?
更新:
这似乎有效
public static void ptrsPointToOutOfOrderElements(Comparable[] a){
int lo = 0;
int hi = a.length-1;
int i = lo;
while(less(a[i],a[i+1])){
if(i+1 == hi){
break;
}
i++;
}
i++;
int j = hi;
while(less(a[j-1],a[j])){
if(j-1 == lo){
break;
}
j--;
}
j--;
for(Comparable x:a){
System.out.print(x+",");
}
System.out.println();
if(i>=j){
System.out.println("pointers crossed");
}
System.out.println("bad element or end of array at i="+i+"==>"+a[i]);
System.out.println("bad element or end of array at j="+j+"==>"+a[j]);
}