抽奖系统问题
2022-10-14 22:08:14 # 算法 # 数据结构 # 堆 #堆

1. 问题描述

有一个抽奖系统，规则如下：

给定两个整数数组，ids代表用户ID列表，ops代表操作，二者等长。对于每一个位置i，如果ops[i]==0，代表ID为ids[i]的用户退了一件货物，ops[i]==1代表他购买了一件货物。有两个区域，一个是获奖区域，一个是候选区域，最多k个人获奖。

如果一个用户购买了一件货物，此时：

  • 如果获奖区域人数没满，且他没进入过获奖区域的话，那么他直接进入获奖区域，以前进入过就不做任何操作。
  • 如果获奖区域的人数满了，那么如果他以前没进入过候选区域，则直接进入候选区域，以前进入过候选区域就不做任何操作。

此时如果发现候选区域的某个人X的购买数量大于获奖区域的某个人（或者某些人）的购买数量的话，则候选区域这个人进入获奖区域，原来获奖区域的人被替换，进入候选区域。如果原来获奖区域多个人的购买数量都小于X的购买数量的话，则替换掉最先进入获奖区域的那个用户。

如果一个用户退了一件货物，此时：

  • 如果他的购买数量已经是0了，抽奖系统不允许购买数量是负数，因此跳过这种情况
  • 如果用户只有最后一件货物了，退了以后，用户的购买数量就是0了， 那么不管他原来在那个区域，都退出原来的区域；

如果他退了一件货物以后，发现获奖区域Y某个人购买数量已经小于候选区域某个人（或者某些人）的购买数量的话，则Y退出获奖区域进入候选区域，候选区域的人进入获奖区域，如果候选区域有多个人的购买数量都大于Y的购买数量的话，那么最早进入候选区域的那个用户进入获奖区域。

总结来说就是，一个抽奖系统，在获奖区域还没满的时候，只要购买数量大于0的用户，都可以直接进入获奖区域；获奖区域满了的话，购买数量大于0的用户则进入候选区域，每一次购买或者退货事件发生的时候，凭着购买数量多，且先到先得的原则，去更新获奖区域。

现在给定这两个数组，编写代码计算每一次购买退货事件发生的时候，获奖区域的用户ID列表。

ops[i]只有0和1两个值

ids[i]可以是任意整数。

k>0

2. 暴力做法

2.1. 算法分析

  1. 使用一个结构保存用户的id，购买数量和进入每个区域的时刻；
  2. 使用哈希表记录每一个id的用户；
  3. 使用list保存获奖区域和候选区域的用户
  4. 每次事件发生的时候，如果还没有更新获奖区域，且候选区域还有人的情况下，按照购买数量升序，到达时间降序对候选区域进行排序，按照按照购买数量降序，到达时间降序对获奖区域排序，用候选区域的最后一个替换获奖区域的最后一个即可。
  5. 收集答案

2.2. 代码

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
import java.util.*;

public class LotteryGameMethod1 {

    public static List<List<Integer>> getLotteryUidList(int[] ids, int[] ops, int k){
        HashMap<Integer,User> map = new HashMap<>();// 这里保存的是购买数量大于0的id和用户的映射。
        ArrayList<User> lotteryArea = new ArrayList<>(),
                candidateArea = new ArrayList<>();
        int i;
        Comparator<User> cntUpTimeDown = (a,b)-> a.cnt!=b.cnt?a.cnt-b.cnt:b.time-a.time,
                cntDownTimeDown = (a,b)->a.cnt!=b.cnt?b.cnt-a.cnt:b.time-a.time;
        List<List<Integer>> ans = new ArrayList<>(ids.length);
        for(i=0; i<ids.length; ++i){
            User user = map.get(ids[i]);
            if(!(user == null && ops[i] == 0)){
                // user == null 表示用户还没买过货物，或者用户买的货物都退了。此时如果还发生退货事件，那么不用理会了
                if(user == null) {
                    user = new User(ids[i],i);
                    map.put(ids[i],user);
                }
                if(ops[i] == 0)--user.cnt;
                else ++user.cnt;
                if(user.cnt == 0){
                    map.remove(ids[i]);
                    lotteryArea.remove(user);
                    candidateArea.remove(user);
                    if(lotteryArea.size() < k && !candidateArea.isEmpty()){
                        // 如果移除的是获奖区域的用户，且候选区域还有人的情况下，需要从候选区域选择一个最好的，放入获奖区域
                        candidateArea.sort(cntUpTimeDown);
                        User candidate = candidateArea.remove(candidateArea.size() - 1);
                        candidate.time = i;
                        lotteryArea.add(candidate);
                    }
                }else{
                    if(lotteryArea.size() < k){
                        if(!lotteryArea.contains(user)) lotteryArea.add(user);
                    }else{
                        if(!candidateArea.contains(user) && !lotteryArea.contains(user)){
                            // 获奖区域已经满了。如果他既不在获奖区域也不在候选区域，那么加入候选区域
                            candidateArea.add(user);
                        }
                        // 排序后，把候选区域购买数量最大的 且来的最早的 和 获奖区域购买数量最小的 且来的最早的，互换
                        if(!candidateArea.isEmpty()){
                            candidateArea.sort(cntUpTimeDown);
                            lotteryArea.sort(cntDownTimeDown);
                            User user1 = candidateArea.get(candidateArea.size() - 1);
                            User user2 = lotteryArea.get(lotteryArea.size() - 1);
                            if(user1.cnt > user2.cnt){
                                user1.time = user2.time = i;
                                candidateArea.set(candidateArea.size() - 1,user2);
                                lotteryArea.set(lotteryArea.size()-1,user1);
                            }
                        }
                    }
                }
            }
            ArrayList<Integer> ansItem = new ArrayList<>(lotteryArea.size());
            for (User lotteryUser : lotteryArea) {
                ansItem.add(lotteryUser.id);
            }
            ans.add(ansItem);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] ids = {1,2,3,3,2,4,5,7,1,1,2,2,2},
                ops={1,1,1,1,1,1,1,1,0,1,0,0,0};
        int k = 2;
        /*
        1
        1,2
        1,2
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        3,4

        * */
        List<List<Integer>> lotteryUidList = getLotteryUidList(ids, ops, k);
        for (List<Integer> integers : lotteryUidList) {
            System.out.println(integers);
        }
    }

    static class User{
        int id,cnt,time;
        public User(int id, int t){
            this.id = id;
            time = t;
        }
    }
}

时间复杂度$O(N^2)$，因为ArrayList删除的时候，时间复杂的是平方级别。

3. 最优解

3.1. 算法分析

上面的平凡解中在每一次事件发生的时候，需要在候选区域中寻找购买数量最多，且来的最早的用户。每次使用排序的方式，效率较低。

我们可以使用堆维护候选区域和获奖区域，候选区域组成 按照购买数量升序，进入时间降序的大顶堆，同时获奖区域 按照购买数量降序，进入时间降序的大顶堆；

则候选区域堆顶就是购买数量最多且来的最早的，获奖区域堆顶就是购买数量最少，且来的最早的。同时堆可以随着元素的添加删除动态调整。

可以在堆结构中加一个contains方法，来判断一个元素是否在堆中。

3.2. 代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class LotteryGameMethod2 {
    public static List<List<Integer>> getLotteryUidList(int[] ids, int[] ops, int k){
        HashMap<Integer,User> map  = new HashMap<>();
        MyHeap<User> lotteryArea = new MyHeap<>((a,b)->a.cnt!= b.cnt?b.cnt-a.cnt:b.time-a.time),
                candidateArea = new MyHeap<>((a,b)->a.cnt!=b.cnt?a.cnt-b.cnt:b.time-a.time);
        List<List<Integer>> ans = new ArrayList<>();
        int i=0,len=ids.length;
        for(;i<len;++i){
            User user = map.get(ids[i]);
            if(!(user==null && ops[i] ==0 )){
                if(user == null){
                    user = new User(ids[i],i);
                    map.put(ids[i],user);
                }
                if(ops[i]==0)--user.cnt;
                else ++user.cnt;
                if(user.cnt == 0){
                    map.remove(ids[i]);
                    lotteryArea.remove(user);
                    candidateArea.remove(user);
                    if (lotteryArea.size()<k && candidateArea.size() >0) {
                        User poll = candidateArea.poll();
                        poll.time = i;
                        lotteryArea.add(poll);
                    }
                }else{
                    if(lotteryArea.size()<k){
                        if(!lotteryArea.contains(user))lotteryArea.add(user);
                        else lotteryArea.update(user);
                    }else{
                        if(!lotteryArea.contains(user) && !candidateArea.contains(user)){
                            candidateArea.add(user);
                        }
                        candidateArea.update(user);
                        lotteryArea.update(user);
                        if(candidateArea.size() > 0 && candidateArea.peek().cnt > lotteryArea.peek().cnt){
                            User candidate = candidateArea.poll();
                            User lottery = lotteryArea.poll();
                            candidate.time = lottery.time = i;
                            candidateArea.add(lottery);
                            lotteryArea.add(candidate);
                        }
                    }
                }
            }
            List<Integer> ansItem = new ArrayList<>(lotteryArea.size());
            for (User lotteryUser : lotteryArea.getAll()) {
                ansItem.add(lotteryUser.id);
            }
            ans.add(ansItem);
        }
        return ans;
    }

    static class User{
        int id, cnt,time;
        public User(int id,int t){
            this.id=id;
            time=t;
        }
    }

    static class MyHeap<T>{

        private ArrayList<T> arrayList;

        private HashMap<T,Integer> indexMap;

        private Comparator<T> comparator;

        private int size;

        public MyHeap(Comparator<T> comparator){
            this.comparator = comparator;
            arrayList = new ArrayList<>();
            indexMap = new HashMap<>();
        }

        public void add(T data){
            indexMap.put(data,size);
            arrayList.add(data);
            heapInsert(size++);
        }

        public void remove(T data){
            Integer index = indexMap.get(data);
            if(index!=null){
                if(index == size-1){
                    arrayList.remove(--size);
                }else {
                    swap(arrayList.get(index),arrayList.get(--size));
                    resign(index);
                    arrayList.remove(size);
                }
                indexMap.remove(data);
            }
        }

        public T poll(){
            T data = arrayList.get(0);
            --size;
            if(size==0){
                arrayList.remove(0);
            }else{
                swap(arrayList.get(0),arrayList.get(size));
                resign(0);
                arrayList.remove(size);
            }
            indexMap.remove(data);
            return data;
        }

        public T peek(){
            return arrayList.get(0);
        }

        public boolean contains(T data){
            return indexMap.containsKey(data);
        }

        public void update(T data){
            Integer index = indexMap.get(data);
            if(index!=null)resign(index);
        }

        public int size(){
            return size;
        }

        public ArrayList<T> getAll(){
            return arrayList;
        }

        private void resign(int index){
            heapInsert(index);
            heapify(index);
        }

        private void heapInsert(int index){
            int parent;
            while(comparator.compare(arrayList.get(index),arrayList.get(parent = (index-1)/2)) > 0){
                swap(arrayList.get(index),arrayList.get(parent));
                index = parent;
            }
        }

        private void heapify(int index){
            int child, bnd = size>>1;
            while(index<bnd){
                child = (index<<1)|1;
                if(child+1<size && comparator.compare(arrayList.get(child),arrayList.get(child+1)) < 0)++child;
                if(comparator.compare(arrayList.get(index),arrayList.get(child)) < 0){
                    swap(arrayList.get(index),arrayList.get(child));
                    index = child;
                }else return;
            }
        }

        private void swap(T t1, T t2){
            Integer index1 = indexMap.get(t1),
                    index2 = indexMap.get(t2);
            arrayList.set(index1,t2);
            arrayList.set(index2,t1);
            indexMap.put(t1,index2);
            indexMap.put(t2,index1);
        }
    }

    public static void main(String[] args) {
        int[] ids = {1,2,3,3,2,4,5,7,1,1,2,2,2},
                ops={1,1,1,1,1,1,1,1,0,1,0,0,0};
        int k = 2;
        /*
        1
        1,2
        1,2
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        2,3
        3,4
        3,4
        * */
        List<List<Integer>> lotteryUidList = getLotteryUidList(ids, ops, k);
        for (List<Integer> integers : lotteryUidList) {
            System.out.println(integers);
        }
    }
}

时间复杂的$O(N\log_2N)$

4. 测试程序

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
import java.util.List;
import java.util.Random;

public class LotteryGameMethodTest {

    public static void main(String[] args) {
        int times = 100_0000,maxArrayLen = 100;
        LotteryGameMethod1 lotteryGameMethod1 = new LotteryGameMethod1();
        LotteryGameMethod2 lotteryGameMethod2 = new LotteryGameMethod2();
        for(int i=0;i<times;++i){
            Random random = new Random();
            int len = random.nextInt(maxArrayLen)+1;
            int[] ids = new int[len], ops = new int[len];
            for(int j =0;j<len;++j){
                ids[j] = random.nextInt(100);
                ops[j] = random.nextInt(2);
            }
            int k = random.nextInt(20)+1;
            List<List<Integer>> lotteryUidList1 = LotteryGameMethod1.getLotteryUidList(ids, ops, k);
            List<List<Integer>> lotteryUidList2 = LotteryGameMethod2.getLotteryUidList(ids, ops, k);
            for(int j = 0;j<len;++j){
                List<Integer> integers1 = lotteryUidList1.get(j);
                List<Integer> integers2 = lotteryUidList2.get(j);
                if(integers1.size()!=integers2.size()){
                    throw new RuntimeException("Oops");
                }
                integers1.sort(Integer::compare);
                integers2.sort(Integer::compare);
                for(int m=0;m<integers1.size();++m){
                    if(!integers1.get(m).equals(integers2.get(m))){
                        throw new RuntimeException("Oops");
                    }
                }
            }
        }
        System.out.println("Test done");
    }
}
上一页
2022-10-14 22:08:14 # 算法 # 数据结构 # 堆 #堆
下一页