给定两个大小相等的数组 nums1 和 nums2,nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列,使其相对于 nums2 的优势最大化。
示例 1:
输入:nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出:[2,11,7,15]
示例 2:
输入:nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出:[24,32,8,12]
提示:
1 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 109
var advantageCount = function(nums1, nums2) {
const n = nums1.length
const i1s = Array.from({length: n}, (_, i) => i)
const i2s = Array.from({length: n}, (_, i) => i)
i1s.sort((a, b) => nums1[a] - nums1[b])
i2s.sort((a, b) => nums2[a] - nums2[b])
const r = new Array(n)
for (let i = 0, left = 0, right = n - 1; i < n; i++) {
if (nums1[i1s[i]] > nums2[i2s[left]]) r[i2s[left++]] = nums1[i1s[i]]
else r[i2s[right--]] = nums1[i1s[i]]
}
return r
};
function advantageCount(nums1: number[], nums2: number[]): number[] {
const n = nums1.length
const i1s = Array.from({length: n}, (_, i) => i)
const i2s = Array.from({length: n}, (_ ,i) => i)
i1s.sort((a, b) => nums1[a] - nums1[b])
i2s.sort((a, b) => nums2[a] - nums2[b])
const r = new Array(n)
for (let i = 0, left = 0, right = n - 1; i < n; i++) {
if (nums1[i1s[i]] > nums2[i2s[left]]) r[i2s[left++]] = nums1[i1s[i]]
else r[i2s[right--]] = nums1[i1s[i]]
}
return r
};
class Solution {
function advantageCount($nums1, $nums2) {
$n = count($nums1);
$i1s = array_fill(0, $n, 0);
$i2s = array_fill(0, $n, 0);
for ($i = 0; $i < $n; $i++) {
$i1s[$i] = $i;
$i2s[$i] = $i;
}
usort($i1s, fn($a, $b) => $nums1[$a] > $nums1[$b]);
usort($i2s, fn($a, $b) => $nums2[$a] > $nums2[$b]);
$r = array_fill(0, $n, 0);
for ($i = 0, $left = 0, $right = $n - 1; $i < $n; $i++) {
if ($nums1[$i1s[$i]] > $nums2[$i2s[$left]]) $r[$i2s[$left++]] = $nums1[$i1s[$i]];
else $r[$i2s[$right--]] = $nums1[$i1s[$i]];
}
return $r;
}
}
func advantageCount(nums1 []int, nums2 []int) []int {
n := len(nums1)
i1s, i2s := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
i1s[i] = i
i2s[i] = i
}
sort.SliceStable(i1s, func(i, j int) bool {
return nums1[i1s[i]] < nums1[i1s[j]]
})
sort.SliceStable(i2s, func(i, j int) bool {
return nums2[i2s[i]] < nums2[i2s[j]]
})
r := make([]int, n)
for i, left, right := 0, 0, n - 1; i < n; i++ {
if nums1[i1s[i]] > nums2[i2s[left]] {
r[i2s[left]] = nums1[i1s[i]]
left++
} else {
r[i2s[right]] = nums1[i1s[i]]
right--
}
}
return r
}
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
Integer[] i1s = new Integer[n], i2s = new Integer[n];
for (int i = 0; i < n; i++) {
i1s[i] = i;
i2s[i] = i;
}
Arrays.sort(i1s, (a, b) -> nums1[a] - nums1[b]);
Arrays.sort(i2s, (a, b) -> nums2[a] - nums2[b]);
int[] r = new int[n];
for (int i = 0, left = 0, right = n - 1; i < n; i++) {
if (nums1[i1s[i]] > nums2[i2s[left]]) {
r[i2s[left]] = nums1[i1s[i]];
left++;
} else {
r[i2s[right]] = nums1[i1s[i]];
right--;
}
}
return r;
}
}
public class Solution {
public int[] AdvantageCount(int[] nums1, int[] nums2) {
int n = nums1.Length;
int[] i1s = new int[n], i2s = new int[n];
for (int i = 0; i < n; i++) {
i1s[i] = i;
i2s[i] = i;
}
Array.Sort(i1s, (a, b) => nums1[a] - nums1[b]);
Array.Sort(i2s, (a, b) => nums2[a] - nums2[b]);
int[] r = new int[n];
for (int i = 0, left = 0, right = n - 1; i < n; i++) {
if (nums1[i1s[i]] > nums2[i2s[left]]) r[i2s[left++]] = nums1[i1s[i]];
else r[i2s[right--]] = nums1[i1s[i]];
}
return r;
}
}
static inline int cmp (const void *pa, const void *pb) {
int *a = (int*)pa, *b = (int*)pb;
return a[1] - b[1];
}
int* advantageCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
int i1s[nums1Size][2], i2s[nums1Size][2];
for (int i = 0; i < nums1Size; i++) {
i1s[i][0] = i, i1s[i][1] = nums1[i];
i2s[i][0] = i, i2s[i][1] = nums2[i];
}
qsort(i1s, nums1Size, sizeof(i1s[0]), cmp);
qsort(i2s, nums1Size, sizeof(i2s[0]), cmp);
int* r = malloc(sizeof(int) * nums1Size);
for (int i = 0, left = 0, right = nums1Size - 1; i < nums1Size; i++) {
if (i1s[i][1] > i2s[left][1]) r[i2s[left++][0]] = i1s[i][1];
else r[i2s[right--][0]] = i1s[i][1];
}
*returnSize = nums1Size;
return r;
}
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> i1s(n), i2s(n);
iota(i1s.begin(), i1s.end(), 0); // populate vector with increasing numbers
iota(i2s.begin(), i2s.end(), 0);
sort(i1s.begin(), i1s.end(), [&nums1, &nums2](int a, int b) {
return nums1[a] < nums1[b];
});
sort(i2s.begin(), i2s.end(), [&nums1, &nums2](int a, int b) {
return nums2[a] < nums2[b];
});
vector<int> r(n);
for (int i = 0, left = 0, right = n - 1; i < n; i++) {
if (nums1[i1s[i]] > nums2[i2s[left]]) r[i2s[left++]] = nums1[i1s[i]];
else r[i2s[right--]] = nums1[i1s[i]];
}
return r;
}
};
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
i1s, i2s = list(range(n)), [i for i in range(n)]
i1s.sort(key = lambda x:nums1[x])
i2s.sort(key = lambda x:nums2[x])
r, left, right = [0] * n, 0, n - 1
for i in range(0, n):
if nums1[i1s[i]] > nums2[i2s[left]]: r[i2s[left]], left = nums1[i1s[i]], left + 1
else: r[i2s[right]], right = nums1[i1s[i]], right - 1
return r