当前位置:首页 » 《我的小黑屋》 » 正文

数据结构-7.Java. 对象的比较

8 人参与  2024年12月07日 16:01  分类 : 《我的小黑屋》  评论

点击全文阅读


本篇博客给大家带来的是java对象的比较的知识点, 其中包括 用户自定义类型比较, PriorityQueue的比较方式, 三种比较方法......

文章专栏: Java-数据结构

若有问题 评论区见

欢迎大家点赞 评论 收藏 分享

如果你不知道分享给谁,那就分享给薯条.

你们的支持是我不断创作的动力 .

1. PriorityQueue中插入对象

上篇文章我们介绍了优先级队列, 优先级队列在插入元素时有个要求:插入的元素不能是 null 或者元素之间必须要能够 进行比较 ,为了简单起见,我们只是插入了 Integer 类型,那优先级队列中能否插入自定义类型对象呢?

class Card {    public int rank; // 数值    public String suit; // 花色    public Card(int rank, String suit) {        this.rank = rank;        this.suit = suit;    }}public class TestPriorityQueue {    public static void TestPriorityQueue()    {        PriorityQueue<Card> p = new PriorityQueue<>();        p.offer(new Card(1, "♠"));        p.offer(new Card(2, "♠"));    }    public static void main(String[] args) {        TestPriorityQueue();    }}

优先级队列底层使用堆,而向堆中插入元素时,为了满足堆的性质,必须要进行元素的比较,而此时 Card 是没有办法直接进行比较的,因此抛出异常。

2.元素的比较

2.1 基本类型的比较

在 Java 中,基本类型的对象可以直接比较大小。
public class TestCompare {    public static void main(String[] args) {        int a = 10;        int b = 20;        System.out.println(a > b);        System.out.println(a < b);        System.out.println(a == b);        char c1 = 'A';        char c2 = 'B';        System.out.println(c1 > c2);        System.out.println(c1 < c2);        System.out.println(c1 == c2);        boolean b1 = true;        boolean b2 = false;        System.out.println(b1 == b2);        System.out.println(b1 != b2);    }}

2.2 对象比较的问题

class Card {    public int rank; // 数值    public String suit; // 花色    public Card(int rank, String suit) {        this.rank = rank;        this.suit = suit;    }}public class TestPriorityQueue {    public static void main(String[] args) {        Card c1 = new Card(1, "♠");        Card c2 = new Card(2, "♠");        Card c3 = c1;        //System.out.println(c1 > c2); // 编译报错        System.out.println(c1 == c2); // 编译成功 ----> 打印false,因为c1和c2指向的是不同对象        //System.out.println(c1 < c2); // 编译报错        System.out.println(c1 == c3); // 编译成功 ----> 打印true,因为c1和c3指向的是同一个对象    }}
c1 、 c2 和 c3 分别是 Card 类型的引用变量,上述代码在比较编译时: c1 > c2 编译失败 c1== c2 编译成功 c1 < c2 编译失败 从编译结果可以看出, Java 中引用类型的变量不能直接按照 > 或者 < 方式进行比较 。 那为什么 == 可以比较呢? 因为: 对于用户实现自定义类型,都默认继承自 Object 类,而 Object类中提供了equal方法 ,而 == 默认情况下调 用的就是 equal 方法 ,但是该方法的比较规则是: 没有比较引用变量引用对象的内容,而是直接比较引用变量的地址 ,但有些情况下该种比较就不符合题意。 记住!!! :  Object 中实现的  equal ,直接比较的是两个引用变量的地址

3. 对象的比较

有些情况下,需要比较的是对象中的内容,比如:向优先级队列中插入某个对象时,需要按照对象中内容来调整 堆,那该如何处理呢?

3.1 重写父类(Object)的equals

class Card {    public int rank; // 数值    public String suit; // 花色    public Card(int rank, String suit) {        this.rank = rank;        this.suit = suit;    }    @Override    public boolean equals(Object o) {        //自己和自己比较        if(this == o) {            return true;        }        //o如果是null对象, 或者o不是Card的子类        if(o == null || !(o instanceof Card)) {            return false;        }        // 注意基本类型可以直接比较,但引用类型最好调用其equal方法        Card c = (Card)o;        return rank == c.rank                && suit.equals(c.suit);    }}
注意: 一般重写 equals 的套路就是上面演示的, (多写几遍, 记住就行!!!) 1. 如果指向同一个对象,返回 true 2. 如果传入的为 null ,返回 false 3. 如果传入的对象类型不是 Card ,返回 false 4. 按照类的实现目标完成比较,例如这里只要花色和数值一样,就认为是相同的牌 5. 注意下调用其他引用类型的比较也需要 equals ,例如这里的 suit 的比较 重写父类 equal()  的方式虽然可以比较,但缺陷是: equal 只能按照相等进行比较,不能按照大于、小于的方式进行 比较

3.2 基于Comparble接口类的比较

Comparble 是 JDK 提供的泛型的比较接口类,源码实现具体如下: 
public interface Comparable<E> {// 返回的值表示的意思:// < 0: 表示 this 指向的对象小于 o 指向的对象// == 0: 表示 this 指向的对象等于 o 指向的对象// > 0: 表示 this 指向的对象大于 o 指向的对象int compareTo(E o);}
对用用户自定义类型,如果要想按照大小与方式进行比较时: 在定义类时,实现Comparble接口即可,然后在类中重写compareTo方法
public class Card implements Comparable<Card>{    public int rank; // 数值    public String suit; // 花色    public Card(int rank, String suit) {        this.rank = rank;        this.suit = suit;    }    // 先根据数值比较,不管花色    // 这里我们认为 null 是最小的    @Override    public int compareTo(Card o) {        if (o == null) {            return 1;        }        return this.rank - o.rank;    }    public static void main(String[] args) {        Card p = new Card(1, "♠");        Card q = new Card(2, "♠");        Card o = new Card(1, "♠");                System.out.println(p.compareTo(o)); // == 0,表示牌相等        System.out.println(p.compareTo(q)); // < 0,表示 p 比较小        System.out.println(q.compareTo(p)); // > 0,表示 q 比较大    }}
Compareble 是 java.lang 中的接口类,可以直接使用。

3.3 基于比较器比较

按照比较器方式进行比较,具体步骤如下:

用户自定义比较器类,实现 Comparator 接口
public interface Comparator<T> {// 返回值表示不同意思:// < 0: 表示 o1 指向的对象小于 o2 指向的对象// == 0: 表示 o1 指向的对象等于 o2 指向的对象// > 0: 表示 o1 指向的对象等于 o2 指向的对象int compare(T o1, T o2);}
注意: 区分  Comparable 和  Comparator复写 Comparator 中的 compare 方法
public class Card {    public int rank; // 数值    public String suit; // 花色    public Card(int rank, String suit) {        this.rank = rank;        this.suit = suit;    }}public static void main(String[] args) {        Card p = new Card(1, "♠");        Card q = new Card(2, "♠");        Card o = new Card(1, "♠");        // 定义比较器对象        CardComparator cmptor = new CardComparator();        // 使用比较器对象进行比较        System.out.println(cmptor.compare(p, o)); // == 0,表示牌相等        System.out.println(cmptor.compare(p, q)); // < 0,表示 p 比较小        System.out.println(cmptor.compare(q, p)); // > 0,表示 q 比较大    }}class CardComparator implements Comparator<Card> {    // 根据数值比较,不管花色// 这里我们认为 null 是最小的    @Override    public int compare(Card o1, Card o2) {        if (o1 == o2) {            return 0;        }        if (o1 == null) {            return -1;        }        if (o2 == null) {            return 1;        }        return o1.rank - o2.rank;    }}
注意: Comparator 是 java.util 包中的泛型接口类,使用时必须导入对应的包, 再重写compare()方法即可.

3.4 三种方式对比

4. 集合框架中PriorityQueue的比较方式

集合框架中的 PriorityQueue 底层使用堆结构,因此其内部的元素必须要能够比大小, PriorityQueue 采用了: Comparble和Comparator 两种方式。 1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法 2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现 Comparator接口并覆写compare方法。 // PriorityQueue 源码 自行在 IDEA 读 就行. 重点还是理解 掌握上面的两种方式.
// JDK中PriorityQueue的实现:public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {//......// 默认容量private static final int DEFAULT_INITIAL_CAPACITY = 11;// 内部定义的比较器对象,用来接收用户实例化PriorityQueue对象时提供的比较器对象private final Comparator<? super E> comparator;// 用户如果没有提供比较器对象,使用默认的内部比较,将comparator置为nullpublic PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}// 如果用户提供了比较器,采用用户提供的比较器进行比较public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {// Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}// ...// 向上调整:// 如果用户没有提供比较器对象,采用Comparable进行比较// 否则使用用户提供的比较器对象进行比较private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}// 使用Comparable@SuppressWarnings("unchecked")private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key;}// 使用用户提供的比较器对象进行比较@SuppressWarnings("unchecked")private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x;}}

5. 使用PriorityQueue创建大小堆,解决TOPK问题

top-k 问题:最大或者最小的前 k 个数据。比如:世界前 500 强公司 链接:  面试题 17.14. 最小K个数 - 力扣(LeetCode) 容易想到的常规做法: 上图两种做法虽然很方便但是 效率不高.  换种做法:  题目要求的是前 k 个最小的数组 我们不妨先把原数组前 k 个元素 建大堆, 然后将 大堆的堆顶元素top 与原数组剩余的元素 [ i ] 进行比较, 若是 top较大 则 top出堆 [ i ] 入堆. 否则就只让 i++即可. 这样一来 比较完之后 堆中的 k 个 元素 必然是 前 k 个最小的元素.  同理, 若是 题目要求前 k 个最大的数组, 则建小堆, top较小 则出堆...... 总结成下图:  下面给出OJ面试的答案, 一定要先自己写, 写不出来了再看答案.
//由于PriorityQueue默认是小根堆, 所以需要实现比较器, 重写compare方法,来创建大根堆.class IntCmp implements Comparator<Integer> {    @Override    public int compare(Integer o1, Integer o2) {        return o2-o1;    }}class Solution {    public int[] smallestK(int[] arr, int k) {        int[] ret = new int[k];        if(arr == null || k <= 0) return ret;        //创建大根堆        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());        for (int i = 0; i < k; i++) {            priorityQueue.offer(arr[i]);        }        for (int j = k; j < arr.length; j++) {            int top = priorityQueue.peek();            if(top > arr[j]) {                //top大, 出堆, 小的元素入堆                priorityQueue.poll();                priorityQueue.offer(arr[j]);            }        }        for(int i = 0;i < k;i++) {            ret[i] = priorityQueue.poll();        }        return ret;    }}

时间复杂度分析: 

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=20fn3gqj5vk00


点击全文阅读


本文链接:http://zhangshiyu.com/post/197658.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1