0


数据结构java版之堆+对象的比较

2022第一天,虎啊虎啊,祝大家虎年大吉!!!本年的第一篇博客来啦

1.问题提出

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

下面让我们一起来看看

①当插入元素为null时:(无论在什么时候插入null,都会报空指针异常)

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

3. 对象的比较

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

注意:当自定义类型要比较两个是不是相同的,内容相同,一定要重写其equals方法

修改代码为:

class Card{
    public int rank;
    public String suit;
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
    @Override
    public boolean equals(Object o) {
//如果this引用和o引用 引用的是同一个对象
        if (this == o) return true;
//getClass()这里比较的是是不是同一个类型,不是的话返回false;当然此处可以用instanceof来判断
//if (o == null || !(o instanceof Card))可以用此语句来代替
        if (o == null || getClass() != o.getClass()) return false;
        Card card = (Card) o;
//数字一样并且花色一样,那么逻辑上就是一样的
        return rank == card.rank && Objects.equals(suit, card.suit);
    }
    @Override
    public int hashCode() {
        return Objects.hash(rank, suit);
    }
}
public class TestDemo {
    public static void main(String[] args) {
        Card card1 = new Card(1, "♥");
        Card card2 = new Card(1, "♥");
        System.out.println(card1.equals(card2));

    }

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

  1. 如果指向同一个对象,返回 true

  2. 如果传入的为 null,返回 false

  3. 如果传入的对象类型不是 Card,返回 false

  4. 按照类的实现目标完成比较,例如这里只要花色和数值一样,就认为是相同的牌

  5. 注意下调用其他引用类型的比较也需要 equals,例如这里的 suit 的比较

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

3.2 基于Comparble接口类的比较

为了具备比较的能力,在这里实现Comparable接口,自己对自己需要的指定部分进行比较(此处默认为小堆的比较)

代码如下:

import java.util.PriorityQueue;
//要具备比较的能力
class Card implements Comparable<Card>{
    public int rank;
    public String suit;
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
    @Override
    public int compareTo(Card o) {
        //自己定义比较的内容
        return o.rank-this.rank;
    }
}
public class TestDemo {
    public static void main(String[] args) {
        //默认底层为小根堆,每存入一个元素均会进行比较
        PriorityQueue<Card>priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(new Card(2,"♥"));//存取第一个元素时实际上是直接放到底层的queue数组的0下标
        priorityQueue.offer(new Card(1,"♥"));
        System.out.println(priorityQueue);

    }

代码如下:

import java.util.Comparator;
import java.util.PriorityQueue;
//要具备比较的能力
class Card{
    public int rank;
    public String suit;
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
}
        class RankCompartor implements Comparator<Card>{
            @Override
            public int compare(Card o1, Card o2) {
                return o1.rank-o2.rank;
            }
        }
public class TestDemo {
    public static void main(String[] args) {
        //默认底层为小根堆,每存入一个元素均会进行比较
    Card card1=new Card(1,"♥");
    Card card2=new Card(2,"♥");
    RankCompartor rankCompartor=new RankCompartor();
    int ret=rankCompartor.compare(card1,card2);
        System.out.println(ret);
    }

同样可以用以下两种方法:

方法①:匿名内部类

 PriorityQueue<Card> priorityQueue = new PriorityQueue<>(new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                return o1.rank-o2.rank;
            }
        });

方法②:lambda表达式


        PriorityQueue<Card> priorityQueue = new PriorityQueue<>((x,y)->{return y.rank-x.rank;});

**3.4 三种方式对比 **

compareTo对类的倾入性比较强

思路①:对整体进行排序,输出前10个最大的元素 。(常规思路)

思路②:用前面刚学过的堆

思路③:a.先把前3个元素创建为小根堆
b.因为当前堆是小根堆,那么堆顶元素一定是前k个元素中较小的元素。如果,存在元素大于堆顶元素,则其替换掉堆顶元素,同时,这个元素有可能就是topk中的一个。相反,若是大根堆,则不一定
c.出出堆顶元素后,便将其再次调整成小根堆


代码如下:

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//求数组中前k个最小的元素,建大堆
public class TopK {
    public static int[] topK(int []array,int k){
        //创建一个大小为k的大根堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //遍历数组当中的元素,将前k个元素放入队列中
        for (int i = 0; i < array.length ; i++) {
            if(maxHeap.size()<k){
                maxHeap.offer(array[i]);
            }else{
                //从k+1个元素开始,每个元素和堆顶元素进行比较
                int top=maxHeap.peek();
                if(top>array[i]){
                    //现将大的弹出
                    maxHeap.poll();
                    //再将小的存入
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[]tmp=new int[k];
        for (int i = 0; i <k ; i++) {
            tmp[i]=maxHeap.poll();

        }
        return tmp;
    }

    public static void main(String[] args) {
        int []array={18,21,8,10,34,12};
        int []tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }
}

堆排序问题:

解题思路:(结束条件为end为0)

①将该堆调整为大根堆

②0下标和最后一个未排序的元素进行交换即可

③end--

④把该堆再次向下调整至大根堆

代码如下:

  public void heapSort() {
        int end = this.usedSize - 1;
        while (end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0, end);
            end--;
        }
    }
  1. 查找和最小的 K 对数字 - 力扣(LeetCode) (leetcode-cn.com)https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/

题目:

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

解题思路:(实际上也是一个topK问题,不同点在于改成了前k个的和的最小的)

???问题在于???如何放一组数对

PriorityQueue<List<Integer>>

代码如下:

  public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
//获取List中的某个元素需要使用get()方法
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
//        for (int i = 0; i < Math.min(nums1.length,k); i++) {
//            for (int j = 0; j < Math.min(nums2.length,k); j++) {
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
//还没放满的情况下
                if(maxHeap.size() < k) {
                    List<Integer> tmpList = new ArrayList<>();
                    tmpList.add(nums1[i]);
                    tmpList.add(nums2[j]);
                    maxHeap.offer(tmpList);
                }else {
//获取顶元素的值
                    int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
                    if(top > nums1[i]+nums2[j]) {
                        //记住  要弹出的
                        maxHeap.poll();
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums1[i]);
                        tmpList.add(nums2[j]);
                        maxHeap.offer(tmpList);
                    }
                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
        List<List<Integer>> ret = kSmallestPairs(nums1,nums2,3);
        System.out.println(ret);
    }

感谢阅读~~~


本文转载自: https://blog.csdn.net/weixin_58850105/article/details/122754361
版权归原作者 反内码者 所有, 如有侵权,请联系我们删除。

“数据结构java版之堆+对象的比较”的评论:

还没有评论