Question

2122. Recover the Original Array

中文文档

Description

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

1. lower[i] = arr[i] - k, for every index i where 0 <= i < n
2. higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return _the original array_ arr. In case the answer is not unique, return _any valid array_.

Note: The test cases are generated such that there exists at least one valid array arr.

 

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12]. 

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

 

Constraints:

• 2 * n == nums.length
• 1 <= n <= 1000
• 1 <= nums[i] <= 109
• The test cases are generated such that there exists at least one valid array arr.

Solutions

Solution 1

class Solution:
  def recoverArray(self, nums: List[int]) -> List[int]:
    nums.sort()
    n = len(nums)
    for i in range(1, n):
      d = nums[i] - nums[0]
      if d == 0 or d % 2 == 1:
        continue
      vis = [False] * n
      vis[i] = True
      ans = [(nums[0] + nums[i]) >> 1]
      l, r = 1, i + 1
      while r < n:
        while l < n and vis[l]:
          l += 1
        while r < n and nums[r] - nums[l] < d:
          r += 1
        if r == n or nums[r] - nums[l] > d:
          break
        vis[r] = True
        ans.append((nums[l] + nums[r]) >> 1)
        l, r = l + 1, r + 1
      if len(ans) == (n >> 1):
        return ans
    return []

class Solution {
  public int[] recoverArray(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1, n = nums.length; i < n; ++i) {
      int d = nums[i] - nums[0];
      if (d == 0 || d % 2 == 1) {
        continue;
      }
      boolean[] vis = new boolean[n];
      vis[i] = true;
      List<Integer> t = new ArrayList<>();
      t.add((nums[0] + nums[i]) >> 1);
      for (int l = 1, r = i + 1; r < n; ++l, ++r) {
        while (l < n && vis[l]) {
          ++l;
        }
        while (r < n && nums[r] - nums[l] < d) {
          ++r;
        }
        if (r == n || nums[r] - nums[l] > d) {
          break;
        }
        vis[r] = true;
        t.add((nums[l] + nums[r]) >> 1);
      }
      if (t.size() == (n >> 1)) {
        int[] ans = new int[t.size()];
        int idx = 0;
        for (int e : t) {
          ans[idx++] = e;
        }
        return ans;
      }
    }
    return null;
  }
}

class Solution {
public:
  vector<int> recoverArray(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1, n = nums.size(); i < n; ++i) {
      int d = nums[i] - nums[0];
      if (d == 0 || d % 2 == 1) continue;
      vector<bool> vis(n);
      vis[i] = true;
      vector<int> ans;
      ans.push_back((nums[0] + nums[i]) >> 1);
      for (int l = 1, r = i + 1; r < n; ++l, ++r) {
        while (l < n && vis[l]) ++l;
        while (r < n && nums[r] - nums[l] < d) ++r;
        if (r == n || nums[r] - nums[l] > d) break;
        vis[r] = true;
        ans.push_back((nums[l] + nums[r]) >> 1);
      }
      if (ans.size() == (n >> 1)) return ans;
    }
    return {};
  }
};

func recoverArray(nums []int) []int {
  sort.Ints(nums)
  for i, n := 1, len(nums); i < n; i++ {
    d := nums[i] - nums[0]
    if d == 0 || d%2 == 1 {
      continue
    }
    vis := make([]bool, n)
    vis[i] = true
    ans := []int{(nums[0] + nums[i]) >> 1}
    for l, r := 1, i+1; r < n; l, r = l+1, r+1 {
      for l < n && vis[l] {
        l++
      }
      for r < n && nums[r]-nums[l] < d {
        r++
      }
      if r == n || nums[r]-nums[l] > d {
        break
      }
      vis[r] = true
      ans = append(ans, (nums[l]+nums[r])>>1)
    }
    if len(ans) == (n >> 1) {
      return ans
    }
  }
  return []int{}
}