package com.lxf;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CanReorderDoubled {
	public static void main(String[] args) {
		System.out.println(canReorderDoubled(new int[] {7,-15,-15,23,-3,80,-35,40,68,22,44,98,20,0,-34,8,40,41,16,46,16,49,-6,-11,35,-15,-74,72,-8,60,40,-2,0,-6,34,14,-16,-92,54,14,-68,82,-30,50,22,25,16,70,-1,-96,11,45,54,40,92,-35,29,80,46,-30,27,7,-70,-37,41,-46,-98,1,-33,-24,-86,-70,80,-43,98,-49,30,0,27,2,82,36,0,-48,3,-100,58,32,90,-22,-50,-12,36,6,-3,-66,72,8,49,-30}));
	}
   public static boolean canReorderDoubled(int[] A) {
	   public static boolean canReorderDoubled(int[] A) {
            Arrays.sort(A);
            Map<Integer, Integer> map=new HashMap<Integer, Integer>();
            //统计0的个数，因为0不符合计算规则，需单独处理
            int countZ=0;
            for (int i = 0; i < A.length; i++) {
                if(A[i]==0) {
                    countZ++;
                }else{
                    //A[i]不为0时
                    //flag:判断当前值是奇数还是偶数
                    boolean flag=A[i]%2==0;
                    if(flag&&map.containsKey(A[i]>>1)&&map.get(A[i]>>1)>0) {
                        //如果为偶数，且它的一半值存在key中，且这个它的一半值key对应的数大于0
                        //则将它的一半值key对应的value--
                        map.put(A[i]>>1, map.get(A[i]>>1)-1);
                    }else if(map.containsKey(A[i]<<1)&&map.get(A[i]<<1)>0) {
                        //如果为奇数或偶数，且它的两倍存在key中，且这个两倍数key对应的数大于0
                        //将它的两倍数key对应的value--
                        map.put(A[i]<<1, map.get(A[i]<<1)-1);
                    }else {
                        //key中无两倍值key或一半值key
                        //将这个数存入map中
                        //第一次存入：初始值为1
                        //多次存入，则是key对应的值++
                        map.put(A[i],map.getOrDefault(A[i], 0)+1);
                    }
                }
            }
            //判端0是否为偶数
            if(countZ%2!=0) {
                return false;
            }
            if(map.values().size()>0) {
                //当map的有value,且value不等于0时，说明有些没有对应的半值或者二倍值
                if(Collections.max(map.values())!=0) {
                    return false;
                }
            }
            return true;
        }
}

2.排序计数(官方题解，稍加修改)

class Solution {
    public boolean canReorderDoubled(int[] A) {
    	//复制A数组到B数组中
        Integer[] B = new Integer[A.length];
        for (int i = 0; i < A.length; ++i)
            B[i] = A[i];
        //将数组取正并排序
        Arrays.sort(B, Comparator.comparingInt(Math::abs));
        //新建一个map存储数字以及它对应的次数
        Map<Integer, Integer> count = new HashMap();
        for (int x: B)
            count.put(x, count.getOrDefault(x, 0) + 1);
		//循环B数组
        for (int x: B) {
            //如果这个值没有了进入下一次循环
            if (count.get(x) == 0) continue;
            //如果这个值的两倍值没有,那么直接返回false
            if (count.getOrDefault(2*x, 0) <= 0) return false;

            //将这两个数减去次数
            count.put(x, count.get(x) - 1);
            count.put(2*x, count.get(2*x) - 1);