《LeetCode刷题》954. 二倍数对数组（java篇）

题目描述：

给定一个长度为偶数的整数数组 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---------------------------------------------------------------------------------------------------------------------------------

day13：今天是一道中等题，思路挺好想的，但是就是不够简洁，也不够快，很优的方法没想到，错了一两次才搞定，要放松放松了，脑瓜子反应都慢了，看看代码：

public boolean canReorderDoubled(int[] arr) {
        int sum = 0, size = arr.length, num = 1;
        List<Integer> list = new ArrayList<>();
        Arrays.sort(arr);
        for (int i = 0; i < size; i++) {
            sum += arr[i];
            list.add(arr[i]);
        }
        if (sum % 3 != 0)
            return false;
        while (list.size() > 0){
            if(num >= list.size())
                return false;
            if (list.get(0) < 0) {
                if (list.get(num) == 0)
                    return false;
                sum = list.get(0) / list.get(num);
                if ((sum > 2) || (sum < 0))
                    return false;
                else if (sum < 2)
                    num++;
                else {
                    list.remove(num);
                    list.remove(0);
                    num = 1;
                }
            }
            else if (list.get(0) == 0){
                if (list.get(num) == 0){
                    list.remove(num);
                    list.remove(0);
                    num = 1;
                }else
                    return false;
            }else {
                sum = list.get(num) / list.get(0) ;
                if (sum > 2)
                    return false;
                else if (sum == 2){
                    list.remove(num);
                    list.remove(0);
                    num = 1;
                }else
                    num ++;
            }
        }
        return true;
    }

 思路解析：

因为数组是乱的，所以先排个序，然后只需要考虑最小的值在后面有没有能匹配的值，如果后面的数已经比它二倍大了就可以不用再往后递增了，如果是负数还要考虑是否一正一副或者被除数为0，这样子算下来太浪费时间了，具体看看下面这种解析：

public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int x : arr) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }
        if (cnt.getOrDefault(0, 0) % 2 != 0) {
            return false;
        }

        List<Integer> vals = new ArrayList<Integer>();
        for (int x : cnt.keySet()) {
            vals.add(x);
        }
        Collections.sort(vals, (a, b) -> Math.abs(a) - Math.abs(b));

        for (int x : vals) {
            if (cnt.getOrDefault(2 * x, 0) < cnt.get(x)) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt.put(2 * x, cnt.getOrDefault(2 * x, 0) - cnt.get(x));
        }
        return true;
    }

 思路解析：

通过哈希表来算值，生成一个哈希表，用来存当前数组，key为数组的值，每出现一次value加1，最终hash表中的key-value就是通过数组值key来存储每个数组出现的次数，如果0出现次数为奇数，直接return，然后用一个列表，把key值也就是原数组填充起来，因为要做排序的操作，列表更方便一点，通过jdk8新特性Collections.sort排绝对值的序，最后通过循环，从最小的往上取，如果2倍key没结果或者2倍key的数比key少，直接rutern false，否则2倍key的个数-key的个数，并覆盖