Question

870. Advantage Shuffle

中文文档

Description

You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].

Return _any permutation of _nums1_ that maximizes its advantage with respect to _nums2.

 

Example 1:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
Output: [24,32,8,12]

 

Constraints:

• 1 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 109

Solutions

Solution 1

class Solution:
  def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()
    t = sorted((v, i) for i, v in enumerate(nums2))
    n = len(nums2)
    ans = [0] * n
    i, j = 0, n - 1
    for v in nums1:
      if v <= t[i][0]:
        ans[t[j][1]] = v
        j -= 1
      else:
        ans[t[i][1]] = v
        i += 1
    return ans

class Solution {
  public int[] advantageCount(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[][] t = new int[n][2];
    for (int i = 0; i < n; ++i) {
      t[i] = new int[] {nums2[i], i};
    }
    Arrays.sort(t, (a, b) -> a[0] - b[0]);
    Arrays.sort(nums1);
    int[] ans = new int[n];
    int i = 0, j = n - 1;
    for (int v : nums1) {
      if (v <= t[i][0]) {
        ans[t[j--][1]] = v;
      } else {
        ans[t[i++][1]] = v;
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    vector<pair<int, int>> t;
    for (int i = 0; i < n; ++i) t.push_back({nums2[i], i});
    sort(t.begin(), t.end());
    sort(nums1.begin(), nums1.end());
    int i = 0, j = n - 1;
    vector<int> ans(n);
    for (int v : nums1) {
      if (v <= t[i].first)
        ans[t[j--].second] = v;
      else
        ans[t[i++].second] = v;
    }
    return ans;
  }
};

func advantageCount(nums1 []int, nums2 []int) []int {
  n := len(nums1)
  t := make([][]int, n)
  for i, v := range nums2 {
    t[i] = []int{v, i}
  }
  sort.Slice(t, func(i, j int) bool {
    return t[i][0] < t[j][0]
  })
  sort.Ints(nums1)
  ans := make([]int, n)
  i, j := 0, n-1
  for _, v := range nums1 {
    if v <= t[i][0] {
      ans[t[j][1]] = v
      j--
    } else {
      ans[t[i][1]] = v
      i++
    }
  }
  return ans
}

function advantageCount(nums1: number[], nums2: number[]): number[] {
  const n = nums1.length;
  const idx = Array.from({ length: n }, (_, i) => i);
  idx.sort((i, j) => nums2[i] - nums2[j]);
  nums1.sort((a, b) => a - b);

  const ans = new Array(n).fill(0);
  let left = 0;
  let right = n - 1;
  for (let i = 0; i < n; i++) {
    if (nums1[i] > nums2[idx[left]]) {
      ans[idx[left]] = nums1[i];
      left++;
    } else {
      ans[idx[right]] = nums1[i];
      right--;
    }
  }
  return ans;
}

impl Solution {
  pub fn advantage_count(mut nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let n = nums1.len();
    let mut idx = (0..n).collect::<Vec<usize>>();
    idx.sort_by(|&i, &j| nums2[i].cmp(&nums2[j]));
    nums1.sort();
    let mut res = vec![0; n];
    let mut left = 0;
    let mut right = n - 1;
    for &num in nums1.iter() {
      if num > nums2[idx[left]] {
        res[idx[left]] = num;
        left += 1;
      } else {
        res[idx[right]] = num;
        right -= 1;
      }
    }
    res
  }
}