Question

2122. 还原原数组

English Version

题目描述

Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：

1. 对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
2. 对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k

不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。

给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。

注意：生成的测试用例保证存在 至少一个 有效数组 arr 。

 

示例 1：

输入：nums = [2,10,6,4,8,12]
输出：[3,7,11]
解释：
如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。

示例 2：

输入：nums = [1,1,3,3]
输出：[2,2]
解释：
如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。

示例 3：

输入：nums = [5,435]
输出：[220]
解释：
唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。

 

提示：

• 2 * n == nums.length
• 1 <= n <= 1000
• 1 <= nums[i] <= 109
• 生成的测试用例保证存在 至少一个 有效数组 arr

解法

方法一

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{}
}