堆练习（二）— 抽奖系统

题目：
题目很长，耐心看完。
给定一个整型数组int[] arr，一个布尔数组boolean[] op，两个数组一定等长，假设长度为N，arr[i]代表客户ID，op[i]表示客户操作 。
arr[3,1,1,4,6]
op [T,T,F,F,T]
代表的意思为，3号客户买了一件商品，1号客户买了1件商品，1号客户退的一件商品，4号客户退了一件商品，6号客户买了一件商品。
每个arr[i]和op[i]都代表着客户的一个事件：T为购买商品，F为退货。
现在，你作为负责人，要在每个事件来时，都给购买次数最多的前K名用户颁奖，所以每个事件发生后，都需要一个获奖名单（得奖区）
得奖规则

1. 如果某个用户购买商品次数为0，但是又发生了退货事件，则认为该事件无效，得奖名单和上一个事件发生后一致，例子中4用户。
2. 用户发生购买商品事件，商品数 + 1，退货事件，商品数 - 1。
3. 每次最多K个用户获奖，K作为参数传入。如果获奖人数不满K个，那就以不够的情况输出。
4. 得奖系统分为得奖区和候选区，只要用户购买了商品，则必在两个区中的一个。
5. 购买数最大的前K名用户进入得奖区，最初时，如果得奖区用户没达到K个，则新来的用户直接进入得奖区。
6. 如果购买数不足以进入得奖区的用户，进入候选区。
7. 如果候选区购买商品数量最多的用户，已经足以进入得奖区，该用户就会替换掉得奖区中购买商品数最少的用户（必须大于才能替换），如果此时得奖区购买数最少的用户有多个（购买商品数相等）
   就替换最早进入得奖区的那个用户，如果候选区购买数最多的用户有多个，则最早进入候选区的用户进入得奖区。
8. 候选区和得奖区是两套时间：
   因为用户只会存在其中一个区域，所以只会有一个区域的时间，另一个没有，从得奖区出来进入候选区的用户，得奖区时间删除
   进入候选区的时间就是当前事件的时间（可以理解为 arr[i] 和 op[i] 中的 i 【下标】）
   从候选区出来进入得奖区的用户，候选区时间删除，
   进入得奖区的时间就是当前事件的时间（同上，数组下标 i）
9. 当用户购买商品数量 == 0时，不管在哪个区域，都会离开，并且区域时间删除，离开指彻底离开，两个区域中都不会存在该用户，如果下次再次购买商品，则商品数量 + 1，根据规则再次进入指定区域。进入区域时间重记。
   终上所述，遍历arr[]和op[]，遍历每一步输出一个获奖名单。

使用常规暴力方法实现

 public static class Customer {
        private int id;
        private int buyNum;
        private int enterTime;

        public Customer(int id, int buyNum, int enterTime) {
            this.id = id;
            this.buyNum = buyNum;
            this.enterTime = enterTime;
        };
    }

    public static class DeJiangQuComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buyNum != o2.buyNum ? (o1.buyNum - o2.buyNum) : o1.enterTime - o2.enterTime;
        }
    }

    public static class HouXuanQuComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o2.buyNum != o1.buyNum ? o2.buyNum - o2.buyNum : o2.enterTime - o1.enterTime;
        }
    }

    public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
        //每一步产生一个获奖名单，获奖名单中会有多个人，所以是个List
        List<List<Integer>> ans = new ArrayList<>();
        //key:用户id  value:具体的用户实例
        Map<Integer, Customer> map = new HashMap<>();
        List<Customer> deJiangQu = new ArrayList<>();
        List<Customer> houXuanQu = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            boolean buyOrRefund = op[i];
            int id = arr[i];
            //如果当前是一个退货操作，并且map中不包含该用户
            //可以理解成脏数据的情况
            if (!buyOrRefund && !map.containsKey(id)) {
                ans.add(getCurAns(deJiangQu));
                continue;
            }
           
            //商品数量 = 0,客户第一次购买
            if (!map.containsKey(id)) {
                map.put(id, new Customer(id, 0, 0));
            }
            //获取到当前的Customer
            Customer c = map.get(id);
            //根据用户行为 buyNum++ 或 buyNum--
            if (buyOrRefund) {
                c.buyNum++;
            } else {
                c.buyNum--;
            }
            //如果操作后，buyNum = 0，则移除
            if (c.buyNum == 0) {
                map.remove(id);
            }
            //如果两个区域都为null， 说明客户可能是第一次进来
            if (!deJiangQu.contains(c) && !houXuanQu.contains(c)) {
                //如果得奖区 当前没满，则直接放入得奖区
                if (deJiangQu.size() < k) {
                    c.enterTime = i;
                    deJiangQu.add(c);
                } else {
                    //否则先放入候选区
                    c.enterTime = i;
                    houXuanQu.add(c);
                }
            }
            //清除掉两个区域中，为0的元素
            clearZeroBuy(deJiangQu);
            clearZeroBuy(houXuanQu);
            //得奖区和候选区进行排序。
            houXuanQu.sort(new HouXuanQuComparator());
            deJiangQu.sort(new DeJiangQuComparator());
            //得奖区和候选区可能出现交换行为
            move(deJiangQu, houXuanQu, k, i);
            ans.add(getCurAns(deJiangQu));
        }
        return ans;
    }

    private static void move(List<Customer> deJiangQu, List<Customer> houXuanQu, int k, int time) {
        //如果候选区此时为null，则不需要进行交换
        if (houXuanQu.isEmpty()){
            return;
        }
        //走到这说明候选区一定有元素
        //但是一定会只有一个值，（比如说K = 3 ,需要3个获奖名单a,b,c，而此时c用户进行了退款，buyNum = 0，进行了删除，那么候选区就应该补进来 ）
        if (deJiangQu.size() < k){
            //取候选区中第1个元素
            Customer c = houXuanQu.get(0);
            //重新设置enterTime
            c.enterTime = time;
            deJiangQu.add(c);
            houXuanQu.remove(0);
        }else{
            //否则，如果得奖区满了，就必须符合下面的条件
            if (houXuanQu.get(0).buyNum > deJiangQu.get(0).buyNum){
                //将两个区域元素进行替换，并删除原有位置
                Customer oldC = deJiangQu.get(0);
                Customer newC = houXuanQu.get(0);
    
                oldC.enterTime = time;
                newC.enterTime = time;

                deJiangQu.add(newC);
                houXuanQu.add(oldC);

                deJiangQu.remove(0);
                houXuanQu.remove(0);
            }
        }
    }

    private static void clearZeroBuy(List<Customer> arr) {
        List<Customer> noZero = new ArrayList<Customer>();
        for (Customer c : arr) {
            if (c.buyNum != 0) {
                noZero.add(c);
            }
        }
        arr.clear();
        for (Customer c : noZero) {
            arr.add(c);
        }
    }

    private static List<Integer> getCurAns(List<Customer> deJiangQu) {
        List<Integer> ans = new ArrayList<>();
        for (Integer num : ans) {
            ans.add(num);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

加强堆方式实现

 public static class LotteryInfo {
        private Map<Integer, Customer> customers;
        private HeapGreater<Customer> hxHeap;
        private HeapGreater<Customer> djHeap;
        private int limit;

        public LotteryInfo(int k) {
            customers = new HashMap<>();
            hxHeap = new HeapGreater<>(new HouXuanQuComparator());
            djHeap = new HeapGreater<>(new DeJiangQuComparator());
            this.limit = k;
        }

        public List<List<Integer>> topK(int[] arr, int[] op, int k) {
            List<List<Integer>> ans = new ArrayList<>();
            LotteryInfo lotteryInfo = new LotteryInfo(k);
            for (int i = 0; i < arr.length; i++) {
                ans.add(lotteryInfo.getCurAns());
            }
            return null;
        }

        private List<Integer> getCurAns() {
            List<Customer> customers = djHeap.getAllElements();
            List<Integer> ans = new ArrayList<>();
            for (Customer c : customers) {
                ans.add(c.id);
            }
            return ans;
        }

        public void operate(int time, int id, boolean buyOrRefund) {
            if (!buyOrRefund && !customers.containsKey(id)) {
                return;
            }
            if (!customers.containsKey(id)) {
                customers.put(id, new Customer(id, 0, 0));
            }
            Customer customer = customers.get(id);
            if (buyOrRefund) {
                customer.buyNum++;
            } else {
                customer.buyNum--;
            }
            if (customer.buyNum == 0) {
                customers.remove(id);
            }
            if (!djHeap.contains(customer) && !hxHeap.contains(customer)) {
                if (djHeap.getSize() < limit) {
                    customer.enterTime = time;
                    djHeap.add(customer);
                } else {
                    customer.enterTime = time;
                    hxHeap.add(customer);
                }
            } else if (hxHeap.contains(customer)) {
                if (customer.buyNum == 0) {
                    hxHeap.remove(customer);
                } else {
                    hxHeap.resign(customer);
                }
            } else {
                if (djHeap.contains(customer)) {
                    if (customer.buyNum == 0) {
                        djHeap.remove(customer);
                    } else {
                        djHeap.resign(customer);
                    }
                }
            }

        }

        public void heapMove(int time) {
            if (hxHeap.isEmpty()) {
                return;
            }
            if (djHeap.getSize() < limit) {
                Customer pop = hxHeap.pop();
                pop.enterTime = time;
                djHeap.add(pop);
            } else {
                if (hxHeap.peek().buyNum > djHeap.peek().buyNum) {
                    Customer oldC = djHeap.pop();
                    Customer newC = hxHeap.pop();

                    oldC.enterTime = time;
                    newC.enterTime = time;
                    djHeap.add(newC);
                    hxHeap.add(oldC);

                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95