高级农民
- 积分
- 2516
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-1-21
- 最后登录
- 1970-1-1
|
第三轮请问楼主用哪2种方法做的?
下面我用2个PQ来做的
注意斯溜舞给出的是交易,我们需要返回的是 int[] {a, b, num}也就是a 还给b $num- public List<int[]> minTransfers(int[][] transactions) {
- // Key: person's ID Value: person's balance after calculation
- // {1 : -5} means person 1 should get $5
- // {2 : 10} means person 2 should pay $10
- Map<Integer, Integer> map = new HashMap<>();
- for (int[] trans : transactions) {
- map.put(trans[0], map.getOrDefault(trans[0], 0) - trans[2]);
- map.put(trans[1], map.getOrDefault(trans[1], 0) + trans[2]);
- }
- // Since after we get those amount of balance, person's ID does not affect the final result
- PriorityQueue<int[]> ownHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1])); // debt owner
- PriorityQueue<int[]> colHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1])); // debt collector
- int n = map.size(), i = 0;
- int[] balance = new int[n];
- for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
- int id = entry.getKey();
- int bal = entry.getValue();
- balance[id] = bal;
- if (bal > 0) {
- ownHeap.offer(new int[]{id, bal});
- } else if (bal < 0) {
- colHeap.offer(new int[]{id, -bal});
- }
- }
- List<int[]> res = new ArrayList<>();
- while (!ownHeap.isEmpty() && !colHeap.isEmpty()) {
- int[] curOwner = ownHeap.poll();
- int curOwnerId = curOwner[0];
- int curOwnerNum = curOwner[1];
- int[] curCollector = colHeap.poll();
- int curCollectorId = curCollector[0];
- int curCollectorNum = curCollector[1];
- int sum = curOwnerNum - curCollectorNum;
- if (sum > 0) {
- ownHeap.offer(new int[]{curOwnerId, sum});
- res.add(new int[]{curOwnerId, curCollectorId, curCollectorNum});
- } else if (sum < 0) {
- colHeap.offer(new int[]{curCollectorId, -sum});
- res.add(new int[]{curOwnerId, curCollectorId, curOwnerNum});
- } else if (sum == 0) {
- res.add(new int[]{curOwnerId, curCollectorId, curOwnerNum});
- }
- }
- return res;
- }
复制代码 |
|