LeetCode 870: Advantage Shuffle
Problem Description
Explanation
To maximize the advantage of nums1 over nums2, we can sort both arrays and then greedily assign each element in nums1 to an element in nums2 such that the advantage is maximized. We can achieve this by using a priority queue (min-heap) to keep track of the elements in nums2 in a sorted manner. We iterate over the sorted nums1 array and for each element, we check if we can find a number in nums2 larger than it. If we find one, we assign it; otherwise, we assign the smallest number in nums2 that hasn't been assigned yet.
Time complexity: O(n log n) where n is the length of nums1 or nums2 (since we are sorting) Space complexity: O(n)
Solutions
import java.util.Arrays;
import java.util.PriorityQueue;
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (int i = 0; i < nums2.length; i++) {
pq.add(new int[]{nums2[i], i});
}
Arrays.sort(nums2);
int low = 0, high = nums1.length - 1;
int[] result = new int[nums1.length];
for (int num : nums1) {
if (num > nums2[low]) {
result[pq.poll()[1]] = num;
low++;
} else {
result[pq.poll()[1]] = num;
}
}
return result;
}
}Related LeetCode Problems
Loading editor...