豆瓣酱1991 2016-02-25 12:23 采纳率: 0%
浏览 1496

java自定义类的数组的二分查找时,应该实现什么接口?

我在做POJ 1054时,希望对自己定义的一个类Plant进行二分查找,但是查找的结果一直不成功(未找到)。我认为是没有实现判断类相等的接口中对应的方法,请问诸位该怎么实现,或者还是别的原因,烦请各位不吝赐教,谢谢!
    以下是源代码,出问题的地方在searchPath方法中”当下一步在稻田内时,查找下一步的坐标是否在Plant[]中“,既:
 if(Arrays.binarySearch(plants, tmp) != -1){
                steps = 0;
                break;
            }

全部代码:

 //POJ 1054
package week1;

import java.util.*;

public class The_Troublesome_frog {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int n = sc.nextInt();

        Plant[] plants = new Plant[n];

        //初始化
        for(int i=0; i<n; i++){
            plants[i] = new Plant();
            plants[i].x = sc.nextInt();
            plants[i].y = sc.nextInt();
        }

        Arrays.sort(plants);
        int maxSteps = 2;
        //选择plant[i]为第一个点,plants[j]为第二个点
        for(int i=0; i<n-2;i++){
            for(int j=i+1; j<n-1; j++){
                int dx = plants[j].x - plants[i].x;
                int dy = plants[j].y - plants[i].y;//在x和y方向上求得青蛙每一步的长度
                int px = plants[i].x - dx;
                int py = plants[i].y - dy;//求按照此步长,第一步之前的一步的位置

                if(px > 1 && px < r && py > 1 && py < c) 
                    continue;
                //如果第一点的前一点在稻田内,说明第二点选的不合适,换一个点做第二点
                int xMax = plants[i].x + (maxSteps - 1) * dx;
                if(xMax > r) 
                    break;
                //未达到目前最长步数-1就出了稻田,说明这条路无法成为当前最长
                //因为x是进过排序的,因此换第二个点只能使得出稻田更快,因此此时要换第一个点
                int yMax = plants[i].y + (maxSteps - 1) * dy;
                if(yMax > c || yMax < 1)
                    continue;
                //Y方向过早越界,换第二个点

                int steps = searchPath(plants[j], plants, dx, dy, r, c);
                if (steps > maxSteps){
                    maxSteps = steps;
                }
                System.out.println("sec" + maxSteps);
            }
            System.out.println("fir" + maxSteps);
        }
        System.out.println("final" + maxSteps);

        sc.close();
    }

    public static int searchPath(Plant secPlant, Plant[] plants, int dx, int dy, int r, int c){
        Plant tmp = new Plant();//表示当前位置
        tmp.x = secPlant.x + dx;
        tmp.y = secPlant.y + dy;
        int steps = 2;
        while(tmp.x < r && tmp.x >1 && tmp.y < c && tmp.y > 1){
            //当下一步在稻田内时,查找下一步的坐标是否在Plants[]中
            if(Arrays.binarySearch(plants, tmp) != -1){
                steps = 0;
                break;
            }
            steps++;
            tmp.x += dx;
            tmp.y += dy;
        }       
        return steps;
    }
}

class Plant implements Comparable<Plant>{
    int x;
    int y;

    public Plant(){
        this.x = 0;
        this.y = 0;
    }
    public int compareTo(Plant p) {
        if(this.x > p.x){
            return 1;
        }
        else{
            if(this.x < p.x) return -1;
            else{
                if(this.y > p.y) return 1;
                else return -1;
            }
        }
    }

    public boolean equals(Plant p){
        if(this.x == p.x && this.y == p.y)
            return true;
        else return false;
    }
}

  • 写回答

2条回答 默认 最新

  • threenewbee 2016-02-25 12:30
    关注

    while(tmp.x < r && tmp.x >1 && tmp.y < c && tmp.y > 1)
    你这里就直接比较了,没有调用compareTo

    评论

报告相同问题?

悬赏问题

  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)