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 <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109
Solutions
Solution 1
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
