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

本篇博客给大家带来的是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;}@Overridepublic 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 是最小的@Overridepublic 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 是最小的@Overridepublic 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置为null
public 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 compatibility
if (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);
else
siftUpComparable(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> {@Overridepublic 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;}
}

时间复杂度分析: