2 u012340794 u012340794 于 2016.02.25 20:23 提问

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个回答

caozhy
caozhy   Ds   Rxr 2016.02.25 20:30

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

enpterexpress
enpterexpress   Rxr 2016.02.25 20:38

直接写在类的方法中

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
含有重复元素的二分查找算法
rust已经有binary_search了,但不能很好的处理有重复元素的查找。 下面这个是我按照网上查找到的原理自己实现的,这个处理重复元素比较好,如果key有重复,那么总是查找到最小的那个indexfn main() { let s = [0, 0,0,0,0,1,1,1, 1, 1, 1, 2,2,3, 3, 5, 8, 13, 21, 34, 55]; let seek = 1
Java实现数组二分查找及递归二分查找
public void binarySearch(int value){ int low = 0; int upper = nElements - 1; int currtIn = (low+upper)/2; while(true){ if(array[currtIn] == value){ System.out.println("find it :_"+currtIn+" "
java数组二分查找
Java数组的二分查找代码,将给定数组排序,然后接收键盘键入的整形数字,并查找该数字。
java 对象数组的排序(实现Comparable接口)和二分查找
package practice;import java.util.Arrays; import java.util.Comparator;/** * Created by fangjiejie on 2016/12/4. */ //正常数组 public class Array { public static void main(String[] args) { int
基于数组二分查找算法的实现
基于数组二分查找算法的实现 二分查找 查找 算法 赵振江 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的
二分查找中term有重复的情况
二分查找算法虽然简单,但是遇到待查找的term重复的时候也会各种小问题。下面给出二分查找中遇到重复term时,第一个可插入位置和最后一个可插入位置的代码。 第一个可插入位置: class Solution { public: int binarySearch(vector &array, int target) { if(array.size() == 0) {
自定义迭代器 iterator接口
内部类方式 package guwa; import java.util.Iterator; public class MyArrayList2 { private String[] elem={"a","b","c","d","e"}; private int size=elem.length; private class Item implements Iterator{
在java用二分查找法实现对数组的排序
二分查找法:前提是数组中的元素要有序,这里只贴自己的图片,至于代码要靠自己写了,毕竟单纯的复制粘贴而不去思考对学习一点用处都没有: 实际上数组已经自带了一个排序算法: Arrays.sort(数组名)为数组排序的操作,但这个方法在java.util这个包里面,所以在用到的时候需要先将它导入, 但这里我们自己写一个算法,加深对排序算法的理解. 运行便可以实现对数组中的元素排序了,就是这么简单…
java实现二分查找-两种方式
二分查找是一种查询效率非常高的查找算法。又称折半查找。 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法 二分查找算法思想 有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。 一个情景:将表中间位置记录的关键字与查找关键字比较,如果两者相等,
Java实现二分查找算法(元素可重复)
public class BinarySearch { public static void main(String[] args) { int[] arrays = new int[]{1,2,3,4,6,6,7,7,8,9,10}; int target = 7; System.out.println(search(arrays, target, 0, arrays.length