Untitled

 avatar
unknown
plain_text
3 months ago
1.1 kB
4
Indexable
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); // Step 1: Sort nums1
        int n = nums1.length;

        // Step 2: Sort nums2 while keeping track of original indices
        int[][] nums2Indexed = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums2Indexed[i] = new int[]{nums2[i], i};
        }
        Arrays.sort(nums2Indexed, (a, b) -> Integer.compare(a[0], b[0]));

        // Step 3: Use a greedy approach with two pointers
        int[] result = new int[n];
        int left = 0, right = n - 1;

        for (int num : nums1) {
            if (num > nums2Indexed[left][0]) {
                result[nums2Indexed[left][1]] = num;
                left++; // Use num to beat the smallest nums2 element
            } else {
                result[nums2Indexed[right][1]] = num;
                right--; // Use num as a "waste" against the largest nums2 element
            }
        }

        return result;
    }
}
Editor is loading...
Leave a Comment