2122. 还原原数组

2122. 还原原数组

周赛t4

双指针+二分

class Solution {
 public:
  vector<int> recoverArray(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    bool vis[n];
    memset(vis, 0, sizeof vis);

    for (int i = 1; i < n; i++) {
      int k = nums[i] - nums[0];
      if (k % 2 || k == 0) continue;
      int left = 0, right = 0;
      memset(vis, false, sizeof vis);

      vector<int> leftarr, rightarr;
      while (right < n) {
        while (left < n && vis[left]) {
          left++;
        }
        int value = nums[left] + k;
        int pos = lower_bound(nums.begin() + right, nums.end(), value) - nums.begin();
        if (pos >= n || value != nums[pos]) break;

        leftarr.push_back(nums[left]);
        rightarr.push_back(nums[pos]);
        vis[left] = vis[pos] = true;

        right = pos + 1;
        left++;
      }
      if (leftarr.size() == n / 2 && rightarr.size() == n / 2) {
        vector<int> res;
        for (int i = 0; i < int(n / 2); i++) {
          res.push_back((leftarr[i] + rightarr[i]) / 2);
        }
        return res;
      }
    }
    return {};
  }
};