力扣954、二倍数对数组

---

最近几天在字节实习，一直在看文档，跑demo，我最大的阻力竟然是电脑是个windows。。。无奈mac缺货，实习生轮不到。不过搞来搞去也是能在windows上调试了，就是有点怪，文档都是mac，windows全靠少量文档和摸索。

好久没刷题了，开始捡起来了。

链接：954. 二倍数对数组

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

输入：arr = [3,1,3,6]
输出：false

示例 2：

输入：arr = [2,1,2,6]
输出：false

示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

提示：

• 0 <= arr.length <= 3 * 104
• arr.length 是偶数
• -105 <= arr[i] <= 105

我的思路

排序，然后记录map，按照正数从大到小的顺序遍历，负数相反的顺序，同时裁剪map，如果遍历到的数找不到一半对应的值，就返回false。

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<arr.length;i++) {
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        Arrays.sort(arr);
        int i=arr.length-1;
        for(;i>0;i--) {
            if(arr[i]<0) break;
            
            if(map.get(arr[i])==0) {
                continue;
            }
            map.put(arr[i],map.get(arr[i])-1);
            if(arr[i]%2==1) return false;
            if(map.getOrDefault(arr[i]/2,0)==0) {
                return false;
            }
            map.put(arr[i]/2,map.get(arr[i]/2)-1);
        }
        
        int j = i;
        for(;j>=0;j--) {
            if(arr[j]>=0) break;
            
             if(map.get(arr[j])==0) {
                continue;
            }
            map.put(arr[j],map.get(arr[j])-1);
            if(map.getOrDefault(arr[j]*2,0)==0) {
                return false;
            }
            map.put(arr[j]*2,map.get(arr[j]*2)-1);
        }
        return true;
    }
}

优先队列

找接近零的数，找2倍，也要map记录2倍数的情况。

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        // 构建最小堆，找最接近零的数（肯定没有/2的数）
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->(Math.abs(a)-Math.abs(b)));
        for(int i=0;i<arr.length;i++) {
            pq.add(arr[i]);
        }
        while(!pq.isEmpty()) {
            int cur = pq.poll();
            if(map.getOrDefault(cur,0)>0) {
                map.put(cur,map.get(cur)-1);
                continue;
            } 
            map.put(cur*2,map.getOrDefault(cur*2,0)+1);
        }
        for(int k:map.keySet()) {
            if(map.get(k)!=0) {
                return false;
            }
        }
        return true;
    }
}

拓扑排序

怎么说呢，这不调试半天不能全A吧。

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> cnt = new HashMap<>();
        int zeroCount = 0;
        for(int i=0;i<arr.length;i++) {
            if (arr[i]==0) {
                zeroCount++;
                continue;
            }
            if(!cnt.containsKey(arr[i])) {
                cnt.put(arr[i],1);
            } else {
                cnt.put(arr[i],cnt.get(arr[i])+1);
            }
        }
        if(zeroCount%2!=0) {
            return false;
        }
        Deque<Integer> zeroInDegree = new LinkedList<>();
        Map<Integer,Integer> inDegree = new HashMap<>();
        
        for(int k:cnt.keySet()) {
            int cur = k;;
            if(cur%2!=0) {
                // 只能作为那个一半的数
                zeroInDegree.add(cur);
            } else {
                // 入度等于/2的个数
                int tmp = cnt.getOrDefault(cur/2,0);
                inDegree.put(cur,tmp);
                if(tmp==0) {
                    zeroInDegree.add(cur);
                }
            }
        }
        int zeroIndNum = 0;
        while(!zeroInDegree.isEmpty()) {
            int cur = zeroInDegree.poll();
            
            int curOutDegree = cnt.get(cur)-inDegree.getOrDefault(cur,0);
            if(curOutDegree==0) {
                continue;
            }
            zeroIndNum+=curOutDegree;
            int curNextCnt = cnt.getOrDefault(cur*2,0);
            if(curNextCnt>=curOutDegree) {
                zeroIndNum+=curOutDegree;
                inDegree.put(cur*2,curOutDegree);
                zeroInDegree.add(cur*2);
                if(curNextCnt==curOutDegree&&cnt.containsKey(cur*4)) {
                    inDegree.put(cur*4,0);
                    zeroInDegree.add(cur*4);
                }
            }else if(curNextCnt<curOutDegree) {
                return false;
            } 
        }
        System.out.println(zeroIndNum);
        if(zeroIndNum+zeroCount==arr.length) {
            return true;
        }
        return false;
    }
}