954. Array of Doubled Pairs

T: O(nlogn + n)
S: O(|hashMap size|)

這個寫法我想還是比較直觀, 雖然要處理 edge case

idea: hashmap 紀錄 num, count

loop array 去找是否有 2*num or num/2 的 count

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Arrays.sort(arr);
        Map<Integer, Integer> map = new HashMap();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        
        for (int num : arr) {
            if (map.get(num) == 0) {
               continue;
            }
            if (num < 0 && num % 2 != 0) { // for [-5,-2], cant cal -5/2 = ??
                return false;
            }
            // negative sort 後會長這樣: -4 -2, 所以要  num/2
            int doubledNum = num < 0 ? num/2 : num*2;
            
            // 找不到對應的 double number
            if (map.getOrDefault(doubledNum, 0) == 0) {
                return false;
            }
            // 都找到 count--
            map.put(num, map.get(num) - 1);
            map.put(doubledNum, map.get(doubledNum) - 1);
        }
        return true;
    }
}

/*

因為沒有要求輸出結果順序, 只是要 true or false
所以一樣的解法可以（leetcode 2007

sort array first
build map

so if small can build large (find in hashmap), map both cnt--
需要注意的是 num < 0 時, 是 num/2, 其他是 num*2

所以也要注意負數一定是偶數, 不然無法 num/2
if (num < 0 && num % 2 != 0) { // for [-5,-2], cant cal -5/2 = ??

T: O(nlogn + n)
S: O(|hashMap size|)

*/

另一種寫法, 只針對 hashmap 的 key 去處理

透過 Integer sort, abs, 可以sort 成 -2, 2, -4, -4這樣就不用處理 num/2

然後應該要 get(num) == get(2*num)

如果 map.get(num) > map.getOrDefault(2*num, 0) => false

這只更新 2*num => map.getOrDefault(2*num, 0) - map.get(num));

Collections.sort(array, (a,b) -> Math.abs(a) - Math.abs(b));

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>(); // <count, count>
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
        }
        List<Integer> array = new ArrayList<>();
        for (int key : map.keySet()) {
            array.add(key);
        }
        
        Collections.sort(array, (a,b) -> Math.abs(a) - Math.abs(b));
        System.out.println(array.toString());
        
        for (int num : array) {
            if (map.get(num) > map.getOrDefault(2*num, 0)) {
                return false;
            }
            map.put(2*num, map.getOrDefault(2*num, 0) - map.get(num));
        }
        return true;
    }
}

/*

  1. 0.1 0
[-2,-4,2,4]


arr[2 * i + 1] = 2 * arr[2 * i]

i = 0, a[1] = 2*a[0]
i = 1, a[3] = 2*a[2]
i = 2, a[5] = 2*a[4]
012345
121212

odd is twice 
*/

use idea same as 2007

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        Collections.sort(list, (a,b) -> {
            if (a < 0 && b < 0) {
                return b - a;
            }
            return a - b;
        });
        int n = list.size();
        Map<Integer, Integer> map = new HashMap<>(); // <2*num, count>
        
        List<Integer> res = new ArrayList<>();
        for (int i = n-1; i >= 0; i--) {
            int num = list.get(i);
            if (!map.containsKey(2*num)) {
                map.put(num, map.getOrDefault(num, 0)+1);
            } else {
                res.add(num);
                map.put(num*2, map.getOrDefault(num*2, 0)-1);
                if (map.get(num*2) == 0) {
                    map.remove(num*2);
                }
            }
        }
        
        return res.size() == n/2;
    }
}

/*
[4,-2,2,-4]

-4 -2 2 4

use same idea with 2007, 但負數要處理

要排序成 
-2 -4 2 4, 所以要改用 list, 才能直接寫 comparator

T: O(nlogn)
S: O(n)
*/