Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/870.html

870. Advantage Shuffle (Medium)

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

 

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

 

Note:

  1. 1 <= A.length = B.length <= 10000
  2. 0 <= A[i] <= 10^9
  3. 0 <= B[i] <= 10^9

Solution 1.

  • class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int length = A.length;
        int[][] arrayA2D = new int[length][2];
        int[][] arrayB2D = new int[length][2];
        for (int i = 0; i < length; i++) {
            arrayB2D[i][0] = B[i];
            arrayB2D[i][1] = i;
        }
        Arrays.sort(arrayB2D, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                return array1[0] - array2[0];
            }
        });
        for (int i = 0; i < length; i++)
            arrayA2D[i][1] = arrayB2D[i][1];
        Arrays.sort(A);
        int index = 0;
        for (int i = 0; i < length; i++) {
            int num = A[i];
            if (num > arrayB2D[index][0]) {
                arrayA2D[index][0] = num;
                index++;
                A[i] = -1;
            }
        }
        for (int i = 0; i < length; i++) {
            int num = A[i];
            if (num >= 0) {
                arrayA2D[index][0] = num;
                index++;
            }
        }
        Arrays.sort(arrayA2D, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                return array1[1] - array2[1];
            }
        });
        int[] permutation = new int[length];
        for (int i = 0; i < length; i++)
            permutation[i] = arrayA2D[i][0];
        return permutation;
    }
}

############

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;
    }
}

  • // OJ: https://leetcode.com/problems/advantage-shuffle/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int N = A.size(), i = 0;
        vector<int> ia(N), ib(N), ans(N, -1);
        iota(begin(ia), end(ia), 0);
        iota(begin(ib), end(ib), 0);
        sort(begin(ia), end(ia), [&](int a, int b) { return A[a] > A[b]; });
        sort(begin(ib), end(ib), [&](int a, int b) { return B[a] > B[b]; });
        for (int j = 0; i < N && j < N; ++i) {
            while (j < N && B[ib[j]] >= A[ia[i]]) ++j;
            if (j < N) {
                ans[ib[j++]] = A[ia[i]];
            } else break;
        }
        for (int j = 0; i < N && j < N; ++i) {
            while (j < N && ans[j] != -1) ++j;
            if (j < N) {
                ans[j++] = A[ia[i]];
            }
        }
        return ans;
    }
};

  • 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

############

class Solution(object):
    def advantageCount(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: List[int]
        """
        res = [-1] * len(A)
        A = collections.deque(sorted(A))
        B = collections.deque(sorted((b, i) for i, b in enumerate(B)))
        for i in range(len(A)):
            a = A.popleft()
            b = B[0]
            if a > b[0]:
                B.popleft()
            else:
                b = B.pop()
            res[b[1]] = a
        return res

  • 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
}

  • 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;
}


  • 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
    }
}

All Problems

All Solutions