最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(7.7)Leetcode上优先队列相关问题

    347. 前K个高频元素

    给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

    例如,

    给定数组 [1,1,1,2,2,3] , 和 k = 2,返回 [1,2]

    注意:

    • 你可以假设给定的 k 总是合理的,1 ≤ k ≤ 数组中不相同的元素的个数。
    • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

    代码演示

    使用我们自己的PriorityQueue

    算法用的是我们自己的PriorityQueue,所以要把所有相关类做成内部类

    import java.util.LinkedList;
    import java.util.List;
    import java.util.TreeMap;
    
    class Solution {
    
        private class Array {
    
            private E[] data;
            private int size;
    
            // 构造函数,传入数组的容量capacity构造Array
            public Array(int capacity){
                data = (E[])new Object[capacity];
                size = 0;
            }
    
            // 无参数的构造函数,默认数组的容量capacity=10
            public Array(){
                this(10);
            }
    
            public Array(E[] arr){
                data = (E[])new Object[arr.length];
                for(int i = 0 ; i < arr.length ; i ++)
                    data[i] = arr[i];
                size = arr.length;
            }
    
            // 获取数组的容量
            public int getCapacity(){
                return data.length;
            }
    
            // 获取数组中的元素个数
            public int getSize(){
                return size;
            }
    
            // 返回数组是否为空
            public boolean isEmpty(){
                return size == 0;
            }
    
            // 在index索引的位置插入一个新元素e
            public void add(int index, E e){
    
                if(index < 0 || index > size)
                    throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    
                if(size == data.length)
                    resize(2 * data.length);
    
                for(int i = size - 1; i >= index ; i --)
                    data[i + 1] = data[i];
    
                data[index] = e;
    
                size ++;
            }
    
            // 向所有元素后添加一个新元素
            public void addLast(E e){
                add(size, e);
            }
    
            // 在所有元素前添加一个新元素
            public void addFirst(E e){
                add(0, e);
            }
    
            // 获取index索引位置的元素
            public E get(int index){
                if(index < 0 || index >= size)
                    throw new IllegalArgumentException("Get failed. Index is illegal.");
                return data[index];
            }
    
            // 修改index索引位置的元素为e
            public void set(int index, E e){
                if(index < 0 || index >= size)
                    throw new IllegalArgumentException("Set failed. Index is illegal.");
                data[index] = e;
            }
    
            // 查找数组中是否有元素e
            public boolean contains(E e){
                for(int i = 0 ; i < size ; i ++){
                    if(data[i].equals(e))
                        return true;
                }
                return false;
            }
    
            // 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
            public int find(E e){
                for(int i = 0 ; i < size ; i ++){
                    if(data[i].equals(e))
                        return i;
                }
                return -1;
            }
    
            // 从数组中删除index位置的元素, 返回删除的元素
            public E remove(int index){
                if(index < 0 || index >= size)
                    throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
                E ret = data[index];
                for(int i = index + 1 ; i < size ; i ++)
                    data[i - 1] = data[i];
                size --;
                data[size] = null; // loitering objects != memory leak
    
                if(size == data.length / 4 && data.length / 2 != 0)
                    resize(data.length / 2);
                return ret;
            }
    
            // 从数组中删除第一个元素, 返回删除的元素
            public E removeFirst(){
                return remove(0);
            }
    
            // 从数组中删除最后一个元素, 返回删除的元素
            public E removeLast(){
                return remove(size - 1);
            }
    
            // 从数组中删除元素e
            public void removeElement(E e){
                int index = find(e);
                if(index != -1)
                    remove(index);
            }
    
            public void swap(int i, int j){
    
                if(i < 0 || i >= size || j < 0 || j >= size)
                    throw new IllegalArgumentException("Index is illegal.");
    
                E t = data[i];
                data[i] = data[j];
                data[j] = t;
            }
    
            @Override
            public String toString(){
    
                StringBuilder res = new StringBuilder();
                res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
                res.append('[');
                for(int i = 0 ; i < size ; i ++){
                    res.append(data[i]);
                    if(i != size - 1)
                        res.append(", ");
                }
                res.append(']');
                return res.toString();
            }
    
            // 将数组空间的容量变成newCapacity大小
            private void resize(int newCapacity){
    
                E[] newData = (E[])new Object[newCapacity];
                for(int i = 0 ; i < size ; i ++)
                    newData[i] = data[i];
                data = newData;
            }
        }
    
        private class MaxHeap> {
    
            private Array data;
    
            public MaxHeap(int capacity){
                data = new Array<>(capacity);
            }
    
            public MaxHeap(){
                data = new Array<>();
            }
    
            public MaxHeap(E[] arr){
                data = new Array<>(arr);
                for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
                    siftDown(i);
            }
    
            // 返回堆中的元素个数
            public int size(){
                return data.getSize();
            }
    
            // 返回一个布尔值, 表示堆中是否为空
            public boolean isEmpty(){
                return data.isEmpty();
            }
    
            // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
            private int parent(int index){
                if(index == 0)
                    throw new IllegalArgumentException("index-0 doesn't have parent.");
                return (index - 1) / 2;
            }
    
            // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
            private int leftChild(int index){
                return index * 2 + 1;
            }
    
            // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
            private int rightChild(int index){
                return index * 2 + 2;
            }
    
            // 向堆中添加元素
            public void add(E e){
                data.addLast(e);
                siftUp(data.getSize() - 1);
            }
    
            private void siftUp(int k){
    
                while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
                    data.swap(k, parent(k));
                    k = parent(k);
                }
            }
    
            // 看堆中的最大元素
            public E findMax(){
                if(data.getSize() == 0)
                    throw new IllegalArgumentException("Can not findMax when heap is empty.");
                return data.get(0);
            }
    
            // 取出堆中最大元素
            public E extractMax(){
    
                E ret = findMax();
    
                data.swap(0, data.getSize() - 1);
                data.removeLast();
                siftDown(0);
    
                return ret;
            }
    
            private void siftDown(int k){
    
                while(leftChild(k) < data.getSize()){
                    int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
                    if( j + 1 < data.getSize() &&
                            data.get(j + 1).compareTo(data.get(j)) > 0 )
                        j ++;
                    // data[j] 是 leftChild 和 rightChild 中的最大值
    
                    if(data.get(k).compareTo(data.get(j)) >= 0 )
                        break;
    
                    data.swap(k, j);
                    k = j;
                }
            }
    
            // 取出堆中的最大元素,并且替换成元素e
            public E replace(E e){
    
                E ret = findMax();
                data.set(0, e);
                siftDown(0);
                return ret;
            }
        }
    
        private interface Queue {
    
            int getSize();
            boolean isEmpty();
            void enqueue(E e);
            E dequeue();
            E getFront();
        }
    
        private class PriorityQueue> implements Queue {
    
            private MaxHeap maxHeap;
    
            public PriorityQueue(){
                maxHeap = new MaxHeap<>();
            }
    
            @Override
            public int getSize(){
                return maxHeap.size();
            }
    
            @Override
            public boolean isEmpty(){
                return maxHeap.isEmpty();
            }
    
            @Override
            public E getFront(){
                return maxHeap.findMax();
            }
    
            @Override
            public void enqueue(E e){
                maxHeap.add(e);
            }
    
            @Override
            public E dequeue(){
                return maxHeap.extractMax();
            }
        }
    
        private class Freq implements Comparable{
    
            public int e, freq;
    
            public Freq(int e, int freq){
                this.e = e;
                this.freq = freq;
            }
    
            @Override
            public int compareTo(Freq another){
                if(this.freq < another.freq)
                    return 1;
                else if(this.freq > another.freq)
                    return -1;
                else
                    return 0;
            }
        }
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>();
            for(int key: map.keySet()){
                if(pq.getSize() < k)
                    pq.enqueue(new Freq(key, map.get(key)));
                else if(map.get(key) > pq.getFront().freq){
                    pq.dequeue();
                    pq.enqueue(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.dequeue().e);
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    使用Java自己的优先队列

    代码1

    import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.TreeMap;
    
    public class Solution {
    
        private class Freq implements Comparable{
    
            public int e, freq;
    
            public Freq(int e, int freq){
                this.e = e;
                this.freq = freq;
            }
    
            public int compareTo(Freq another){
                if(this.freq < another.freq)
                    return -1;
                else if(this.freq > another.freq)
                    return 1;
                else
                    return 0;
            }
        }
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>();
            for(int key: map.keySet()){
                if(pq.size() < k)
                    pq.add(new Freq(key, map.get(key)));
                else if(map.get(key) > pq.peek().freq){
                    pq.remove();
                    pq.add(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    代码2

    import java.util.*;
    
    public class Solution2 {
    
        private class Freq{
    
            public int e, freq;
    
            public Freq(int e, int freq){
                this.e = e;
                this.freq = freq;
            }
        }
    
        private class FreqComparator implements Comparator{
    
            @Override
            public int compare(Freq a, Freq b){
                return a.freq - b.freq;
            }
        }
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>(new FreqComparator());
            for(int key: map.keySet()){
                if(pq.size() < k)
                    pq.add(new Freq(key, map.get(key)));
                else if(map.get(key) > pq.peek().freq){
                    pq.remove();
                    pq.add(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    代码3

    import java.util.*;
    
    public class Solution3 {
    
        private class Freq{
    
            public int e, freq;
    
            public Freq(int e, int freq){
                this.e = e;
                this.freq = freq;
            }
        }
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>(new Comparator() {
                @Override
                public int compare(Freq a, Freq b) {
                    return a.freq - b.freq;
                }
            });
            for(int key: map.keySet()){
                if(pq.size() < k)
                    pq.add(new Freq(key, map.get(key)));
                else if(map.get(key) > pq.peek().freq){
                    pq.remove();
                    pq.add(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    代码4

    import java.util.*;
    
    public class Solution4 {
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>(new Comparator() {
                @Override
                public int compare(Integer a, Integer b) {
                    return map.get(a) - map.get(b);
                }
            });
            for(int key: map.keySet()){
                if(pq.size() < k)
                    pq.add(key);
                else if(map.get(key) > map.get(pq.peek())){
                    pq.remove();
                    pq.add(key);
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove());
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    代码5

    import java.util.*;
    
    public class Solution5 {
    
        public List topKFrequent(int[] nums, int k) {
    
            TreeMap map = new TreeMap<>();
            for(int num: nums){
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue pq = new PriorityQueue<>(
                    (a, b) -> map.get(a) - map.get(b)
                );
            for(int key: map.keySet()){
                if(pq.size() < k)
                    pq.add(key);
                else if(map.get(key) > map.get(pq.peek())){
                    pq.remove();
                    pq.add(key);
                }
            }
    
            LinkedList res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove());
            return res;
        }
    
        private static void printList(List nums){
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }
    

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(7.7)Leetcode上优先队列相关问题

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 192会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 614稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级