Question

954. Array of Doubled Pairs

中文文档

Description

Given an integer array of even length arr, return true_ if it is possible to reorder _arr_ such that _arr[2 * i + 1] = 2 * arr[2 * i]_ for every _0 <= i < len(arr) / 2_, or _false_ otherwise_.

 

Example 1:

Input: arr = [3,1,3,6]
Output: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

 

Constraints:

• 2 <= arr.length <= 3 * 104
• arr.length is even.
• -105 <= arr[i] <= 105

Solutions

Solution 1

class Solution:
  def canReorderDoubled(self, arr: List[int]) -> bool:
    freq = Counter(arr)
    if freq[0] & 1:
      return False
    for x in sorted(freq, key=abs):
      if freq[x << 1] < freq[x]:
        return False
      freq[x << 1] -= freq[x]
    return True

class Solution {
  public boolean canReorderDoubled(int[] arr) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : arr) {
      freq.put(v, freq.getOrDefault(v, 0) + 1);
    }
    if ((freq.getOrDefault(0, 0) & 1) != 0) {
      return false;
    }
    List<Integer> keys = new ArrayList<>(freq.keySet());
    keys.sort(Comparator.comparingInt(Math::abs));
    for (int k : keys) {
      if (freq.getOrDefault(k << 1, 0) < freq.get(k)) {
        return false;
      }
      freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k));
    }
    return true;
  }
}

class Solution {
public:
  bool canReorderDoubled(vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int& v : arr) ++freq[v];
    if (freq[0] & 1) return false;
    vector<int> keys;
    for (auto& [k, _] : freq) keys.push_back(k);
    sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
    for (int& k : keys) {
      if (freq[k * 2] < freq[k]) return false;
      freq[k * 2] -= freq[k];
    }
    return true;
  }
};

func canReorderDoubled(arr []int) bool {
  freq := make(map[int]int)
  for _, v := range arr {
    freq[v]++
  }
  if freq[0]%2 != 0 {
    return false
  }
  var keys []int
  for k := range freq {
    keys = append(keys, k)
  }
  sort.Slice(keys, func(i, j int) bool {
    return abs(keys[i]) < abs(keys[j])
  })
  for _, k := range keys {
    if freq[k*2] < freq[k] {
      return false
    }
    freq[k*2] -= freq[k]
  }
  return true
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}