class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
}
};
870. 优势洗牌
给定两个大小相等的数组 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 <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109原站题解
python3 解法, 执行用时: 156 ms, 内存消耗: 33.7 MB, 提交时间: 2023-06-27 17:38:59
# 田忌赛马
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
ans = [0] * n
nums1.sort()
ids = sorted(range(n), key=lambda i: nums2[i])
left, right = 0, n - 1
for x in nums1:
if x > nums2[ids[left]]:
ans[ids[left]] = x # 用下等马比下等马
left += 1
else:
ans[ids[right]] = x # 用下等马比上等马
right -= 1
return ans
java 解法, 执行用时: 64 ms, 内存消耗: 56.7 MB, 提交时间: 2023-06-27 17:38:19
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
var n = nums1.length;
var ans = new int[n];
Arrays.sort(nums1);
var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(ids, (i, j) -> nums2[i] - nums2[j]);
int left = 0, right = n - 1;
for (var x : nums1)
ans[x > nums2[ids[left]] ? ids[left++] : ids[right--]] = x;
return ans;
}
}
golang 解法, 执行用时: 120 ms, 内存消耗: 9.3 MB, 提交时间: 2023-06-27 17:37:53
func advantageCount(nums1, nums2 []int) []int {
n := len(nums1)
ans := make([]int, n)
sort.Ints(nums1)
ids := make([]int, n)
for i := range ids {
ids[i] = i
}
sort.Slice(ids, func(i, j int) bool { return nums2[ids[i]] < nums2[ids[j]] })
left, right := 0, n-1
for _, x := range nums1 {
if x > nums2[ids[left]] {
ans[ids[left]] = x // 用下等马比下等马
left++
} else {
ans[ids[right]] = x // 用下等马比上等马
right--
}
}
return ans
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 57 MB, 提交时间: 2023-06-27 17:37:38
// 田忌赛马
class Solution {
public:
vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2) {
int n = nums1.size(), ids[n];
vector<int> ans(n);
sort(nums1.begin(), nums1.end());
iota(ids, ids + n, 0);
sort(ids, ids + n, [&](int i, int j) { return nums2[i] < nums2[j]; });
int left = 0, right = n - 1;
for (int x : nums1)
ans[x > nums2[ids[left]] ? ids[left++] : ids[right--]] = x;
return ans;
}
};