当前位置: 首页 > news >正文

初学数据结构:Java对象的比较

目录

    • 1. PriorityQueue中插入对象
    • 2. 元素的比较
      • 2.1 基本类型的比较
      • 2.2 对象比较的问题
    • 3. 对象的比较
      • 3.1 基于Comparable接口类的比较
      • 3.2 基于比较器比较
      • 3.3 三种方式对比
    • 4. 集合框架中PriorityQueue的比较方式
    • 5. 使用PriorityQueue创建大小堆,解决TOPK问题

【本节目标】

  1. Java中对象的比较
  2. 集合框架中PriorityQueue的比较方式
  3. 模拟实现PriorityQueue

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指向的是同一个对象}
}

从编译结果可以看出,Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。 那为什么==可以比较?

因为:对于用户实现自定义类型,都默认继承自Object类,而Object类中提供了equal方法,而==默认情况下调用的就是equal方法,但是该方法的比较规则是:没有比较引用变量引用对象的内容,而是直接比较引用变量的地址,但有些情况下该种比较就不符合题意。

// Object中equal的实现,可以看到:直接比较的是两个引用变量的地址
public boolean equals(Object obj) {return (this == obj);
}

3. 对象的比较

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

public 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 this.rank == c.rank && suit.equals(c.suit);}
}

注意: 一般覆写 equals 的套路就是上面演示的

  1. 如果指向同一个对象,返回 true
  2. 如果传入的为 null,返回 false
  3. 如果传入的对象类型不是 Card,返回 false
  4. 按照类的实现目标完成比较,例如这里只要花色和数值一样,就认为是相同的牌
  5. 注意调用其他引用类型的比较也需要 equals,例如这里的 suit 的比较

覆写基类equal的方式虽然可以比较,但缺陷是:equal只能按照相等进行比较,不能按照大于、小于的方式进行比较。

3.1 基于Comparable接口类的比较

Comparable是JDK提供的泛型的比较接口类,源码实现具体如下

public interface Comparable<E> {// 返回值:// < 0: 表示 this 指向的对象小于 o 指向的对象// == 0: 表示 this 指向的对象等于 o 指向的对象// > 0: 表示 this 指向的对象大于 o 指向的对象int compareTo(E o);
}

对用用户自定义类型,如果要想按照大小与方式进行比较时:在定义类时,实现Comparable接口即可,然后在类中重写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 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 比较大}
}

Comparable是java.lang中的接口类,可以直接使用

3.2 基于比较器比较

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

  1. 用户自定义比较器类,实现Comparator接口

    public interface Comparator<T> {// 返回值:// < 0: 表示 o1 指向的对象小于 o2 指向的对象// == 0: 表示 o1 指向的对象等于 o2 指向的对象// > 0: 表示 o1 指向的对象等于 o2 指向的对象int compare(T o1, T o2);
    }
    

    注意:区分Comparable和Comparator

  2. 覆写Comparator中的compare方法

    import java.util.Comparator;
    class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}
    }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;}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 比较大}
    }
    

    注意:Comparator是java.util 包中的泛型接口类,使用时必须导入对应的包

3.3 三种方式对比

覆写的方法说明
Object.equals因为所有类都是继承自 Object 的,所以直接覆写即可,不过只能比较相等与否
Comparable.compareTo需要手动实现接口,侵入性比较强,但一旦实现,每次用该类都有顺序,属于内部顺序
Comparator.compare需要实现一个比较器对象,对待比较类的侵入性弱,但对算法代码实现侵入性强

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

集合框架中的PriorityQueue底层使用堆结构,因此其内部的元素必须要能够比大小,PriorityQueue采用了: Comparable和Comparator两种方式

  1. Comparable是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparable接口,并覆写compareTo方法
  2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法
// 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问题

//使用比较器创建小根堆
class LessIntComp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}
} 
//使用比较器创建大根堆
class GreaterIntComp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}
public class TestDemo<E> {//求最小的K个数,通过比较器创建大根堆public static int[] smallestK(int[] array, int k) {if(k <= 0) {return null;} GreaterIntComp greaterCmp = new GreaterIntComp();PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp);//先将前K个元素,创建大根堆for(int i = 0; i < k; i++) {maxHeap.offer(array[i]);} //从第K+1个元素开始,每次和堆顶元素比较for (int i = k; i < array.length; i++) {int top = maxHeap.peek();if(array[i] < top) {maxHeap.poll();maxHeap.offer(array[i]);}} //取出前K个int[] ret = new int[k];for (int i = 0; i < k; i++) {int val = maxHeap.poll();ret[i] = val;} return ret;}public static void main(String[] args) {int[] array = {4,1,9,2,8,0,7,3,6,5};int[] ret = smallestK(array,3);System.out.println(Arrays.toString(ret));}
}

相关文章:

初学数据结构:Java对象的比较

目录 1. PriorityQueue中插入对象2. 元素的比较2.1 基本类型的比较2.2 对象比较的问题 3. 对象的比较3.1 基于Comparable接口类的比较3.2 基于比较器比较3.3 三种方式对比 4. 集合框架中PriorityQueue的比较方式5. 使用PriorityQueue创建大小堆&#xff0c;解决TOPK问题 【本节…...

mac 10.15.7 Unity 2021.3.14 XCode 12.4 -> Unity IOS 自动安装 Cocoapods 失败解决方法

自己这两天在用Unity开发IOS时&#xff0c;遇到了安装Cocoapods失败的问题&#xff0c;记录一下问题及解决方法&#xff0c;便于自己后续查看&#xff0c;以及有相同遭遇的人查看 发生场景&#xff1a;打开 unity&#xff0c;触发自动安装 Cocoapods -> 安装失败&#xff08…...

Elasticsearch 中使用MustNot等同于不登录遇到的坑

1、在写关键词推荐时,需要把当前文章过滤掉,不能再推荐自己的文章,所以再es中需要用到 MustNot属性查询 /// <summary> /// 服务中心es检索 /// </summary> /// <param name="input"></param> /// <returns></…...

java抽象工厂实战与总结

文章目录 一、工厂模式&#xff08;三种&#xff09;1.简单工厂模式1.1 概念&#xff1a;1.2 使用场景&#xff1a;1.3 模型图解&#xff1a;1.4 伪代码&#xff1a; 2.工厂方法模式2.1 概念&#xff1a;2.2 使用场景&#xff1a;2.3 模型图解&#xff1a;2.4 伪代码 3.抽象工厂…...

Compose | UI组件(六) | 选择框

文章目录 前言Checkbox 复选框的含义Checkbox 复选框的使用Switch 单选框的含义Switch 单选框的使用Slider 滑竿组件的含义Slider 滑竿组件的使用 总结 前言 随着移动端的技术不断更新迭代&#xff0c;Compose也运用的越来越广泛&#xff0c;很多人都开始学习Compose 本文主要…...

C++拷贝构造函数、赋值学习整理:

拷贝构造函数&#xff1a; 概念&#xff1a; 构造函数的第一个参数&#xff0c;是类本身的const引用&#xff08;一般情况下没有其他参数&#xff0c;少数情况&#xff1a;其他参数必须有默认值&#xff01;&#xff09;称此类构造函数为拷贝构造函数 特征&#xff1a; 1&am…...

[亲测源码]ps软件网页版在线使用 PS网站程序源码 photoshop网页版源码 网页版的ps软件源码

在线PS作图修图网页版PHP网站源码&#xff0c;PHP在线照片图片处理PS网站程序源码photoshop网页版。 有很多朋友们都是在用PS作图的&#xff0c;众所周知在使用和学习PS时是需要下载软件的&#xff0c;Photoshop软件对电脑配置也是有一定要求的&#xff0c;今天就为大家带来一…...

前端大厂面试题探索编辑部——第二期

目录 题目 单选题1 题解 关于TCP 关于UDP 单选题2 题解 A选项的HTTP是否是无状态协议 B选项的HTTP支持的方法 C选项的关于HTTP的状态码 D选项HTTP协议的传输格式 题目 单选题1 1.以下哪个描述是关于 TCP 和 UDP 的区别&#xff08;&#xff09; A. TCP 是无连接的…...

yaml学习笔记

文章目录 yaml语言学习yaml 简介yaml 和json 区别基本语法数据类型YAML 对象YAML 数组锚点和引用纯量 参考文档 yaml语言学习 最近发现在学习k8s中各种配置文件 都是使用的yaml 这种格式, 包括 docker-compose.yaml 也都是用这个格式配置部署项目信息,我就了解了一下这个语法就…...

深度强化学习(王树森)笔记04

深度强化学习&#xff08;DRL&#xff09; 本文是学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。本文在ChatGPT辅助下完成。 参考链接 Deep Reinforcement Learning官方链接&#xff1a;https://github.com/wangshusen/DRL 源代码链接&#xff1a;https://github.c…...

openssl3.2/test/certs - 074 - CT entry

文章目录 openssl3.2/test/certs - 074 - CT entry概述笔记setup074.shsetup074_sc1.shsetup074_sc2.shsetup074_sc3.shEND openssl3.2/test/certs - 074 - CT entry 概述 openssl3.2 - 官方demo学习 - test - certs 笔记 setup074.sh #! /bin/bash# \file setup074.sh# o…...

Angular组件(一) 分割面板ShrinkSplitter

Angular组件(一) 分割面板ShrinkSplitter 前言 分割面板在日常开发中经常使用&#xff0c;可将一片区域&#xff0c;分割为可以拖拽整宽度或高度的两部分区域。模仿iview的分割面板组件&#xff0c;用angular实现该功能&#xff0c;支持拖拽和[(ngModel)]双向绑定的方式控制区…...

抖音详情API:视频内容获取与解析技巧

一、引言 抖音是一款广受欢迎的短视频分享平台&#xff0c;每天都有大量的用户在抖音上分享自己的生活点滴和创意作品。对于开发者而言&#xff0c;如何获取并解析抖音上的视频内容&#xff0c;是一项极具挑战性的任务。本文将详细介绍抖音详情API&#xff0c;以及如何使用它来…...

SpringBoot中实现阿里云OSS对象存储

背景 在业务中我们往往需要上传文件如图片&#xff0c;文件上传&#xff0c;是指将本地图片、视频、音频等文件上传到服务器上&#xff0c;可以供其他用户浏览或下载的过程。文件上传在项目中应用非常广泛&#xff0c;我们经常发抖音、发朋友圈都用到了文件上传功能。 实现文件…...

大型语言模型 (LLM)全解读

一、大型语言模型&#xff08;Large Language Model&#xff09;定义 大型语言模型 是一种深度学习算法&#xff0c;可以执行各种自然语言处理 (NLP) 任务。 大型语言模型底层使用多个转换器模型&#xff0c; 底层转换器是一组神经网络。 大型语言模型是使用海量数据集进行训练…...

Unity - gamma space下还原linear space效果

文章目录 环境目的环境问题实践结果处理要点处理细节【OnPostProcessTexture 实现 sRGB 2 Linear 编码】 - 预处理【封装个简单的 *.cginc】 - shader runtime【shader需要gamma space下还原记得 #define _RECOVERY_LINEAR_IN_GAMMA】【颜色参数应用前 和 颜色贴图采样后】【灯…...

Rabbitmq调用FeignClient接口失败

文章目录 一、框架及逻辑介绍1.背景服务介绍2.问题逻辑介绍 二、代码1.A服务2.B服务3.C服务 三、解决思路1.确认B调用C服务接口是否能正常调通2.确认B服务是否能正常调用A服务3.确认消息能否正常消费4.总结 四、修改代码验证1.B服务异步调用C服务接口——失败2.将消费消息放到C…...

专业120+总分400+海南大学838信号与系统考研高分经验海大电子信息与通信

今年专业838信号与系统120&#xff0c;总分400&#xff0c;顺利上岸海南大学&#xff0c;这一年的复习起起伏伏&#xff0c;但是最后还是坚持下来的&#xff0c;吃过的苦都是值得&#xff0c;总结一下自己的复习经历&#xff0c;希望对大家复习有帮助。首先我想先强调一下专业课…...

如何区分 html 和 html5?

HTML&#xff08;超文本标记语言&#xff09;和HTML5在很多方面都存在显著的区别。HTML5是HTML的最新版本&#xff0c;引入了许多新的特性和元素&#xff0c;以支持更丰富的网页内容和更复杂的交互。以下是一些区分HTML和HTML5的关键点&#xff1a; 新特性与元素&#xff1a;H…...

Ps:将文件载入堆栈

Ps菜单&#xff1a;文件/脚本/将文件载入堆栈 Scripts/Load Files into Stack 将文件载入堆栈 Load Files into Stack脚本命令可用于将两个及以上的文件载入到同一个 Photoshop 新文档中。 载入的每个文件都将成为独立的图层&#xff0c;并使用其原始文件名作为图层名。 Photos…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...