网易4.18笔试----数据分析

求问第三道编程题。求中位数获奖的那个
我的思路是利用一个大顶堆、一个小顶堆(根据score排序)。一分为二数据。所有数据中相对较大的进入到小顶堆。相对较小的进入到大顶堆。如果他们size()相同就进入到小顶堆。反之进入到大顶堆。这样可以保证中位数就是两个堆顶元素的两者求平均或者就是小顶堆的堆顶元素。参见Leecode 剑指 Offer 41
数据流中的中位数 做法
我不明白我为什么错了,求指教

package WangyiTwo;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MidNum {
    public static void main(String[] args) {
        // 这个作为大顶堆
        PriorityQueue<Player>queuelow = new PriorityQueue<Player>(new Comparator<Player>() {
            @Override
            public int compare(Player o1, Player o2) {
                return o2.score - o1.score;
            }
        });

        // 小顶堆 存放两个数字中较大的
        PriorityQueue<Player>queuehigh = new PriorityQueue<>(new Comparator<Player>() {
            @Override
            public int compare(Player o1, Player o2) {
                return o1.score - o2.score;
            }
        });



        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        for(int i = 0; i < n; i++){
            int k = Integer.parseInt(sc.nextLine());// 记录总数
            int count = 0;
            for(int j = 0; j < k; j++){
                String[] str = sc.nextLine().split(" ");
                Player player = new Player(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
                boolean flag = store(queuelow, queuehigh, player);
                if (flag){
                    // 表示更新或者上榜
                    // 获取中位数
                    double num = getmid(queuelow, queuehigh);
                    if(num == (double) player.score && !player.award){
                        player.award = true;
                        count++;
                    }
                }
            }
            System.out.println(count);
        }


    }


    private static boolean store(PriorityQueue<Player>queuelow, PriorityQueue<Player>queuehigh, Player player){

        boolean flag1 = false;
        boolean flag2 = false;
        // 要判断player是否存在于队列之中
        for (Player player1 : queuelow) {
            if(player1.id == player.id){
                if(player1.score < player.score){
                    if (player1.award){
                        player.award = true;
                    }
                    queuelow.remove(player1);
                    flag1 = true;
                    break;
                }
                else {
                    // 就不需要在存储了
                    return false;
                }
            }
        }

        if (flag1){
            // 说明出现在queuelow中
            // 这时候queuelow的元素比queuehigh少
            queuehigh.add(player);
            Player p = queuehigh.poll();
            queuelow.add(p);
            return true;
        }
        else{
            for (Player player1 : queuehigh) {
                if(player1.id == player.id){
                    if(player1.score < player.score){
                        if (player1.award){
                            player.award = true;
                        }
                        queuehigh.remove(player1);
                        flag2 = true;
                        break;
                    }
                    else {
                        return false;
                    }

                }
            }
        }

        if(flag2){
            // 说明是出现在queuehigh中
            // 此时看m 与n的大小
            queuelow.add(player);
            Player p = queuelow.poll();
            queuehigh.add(p);
            return true;
        }

        // 在queuelow 和 queuehigh中都不存在
        int m = queuelow.size();
        int n = queuehigh.size();

        if(m == n){
            // 将player先加入到queuelow,然后将queuelow中的队头元素给到queuehigh
            queuelow.add(player);
            Player p = queuelow.poll();
            queuehigh.add(p);

        }
        else {
            // m > n就先添加到queuehigh然后将queuehigh中的队头元素给queuelow
            queuehigh.add(player);
            Player p = queuehigh.poll();
            queuelow.add(p);
        }
        return true;
    }

    private static double getmid(PriorityQueue<Player>queuelow, PriorityQueue<Player>queuehigh){
        int m = queuelow.size();
        int n = queuehigh.size();
        if(m == n){
            int num1 = queuehigh.peek().score;
            int num2 = queuelow.peek().score;
            double c = (num1 + num2) / 2.0;
            return c;
        }
        else {
            return (double) queuehigh.peek().score;
        }
    }
}

class Player{
    public int id;
    public int score;
    public boolean award;

    public Player(int id, int score) {
        this.id = id;
        this.score = score;
        this.award = false;
    }
}
#网易##笔试题目#
全部评论
我和你思路差不多,但没写出来,最后暴力过了90%😂
点赞 回复
分享
发布于 2021-04-18 17:31

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务