# Problem

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: Greedy 田忌赛马

Use the smallest unused number A[j] in A such that A[j] > B[i], if not possible, use the smallest number in A.

Time complexity: O(nlogn)

Space complexity: O(n)

C++

# Problem

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.


Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.


Note:

• A will be a permutation of [0, 1, ..., A.length - 1].
• A will have length in range [1, 5000].
• The time limit for this problem has been reduced.

# Solution1: Brute Force (TLE)

Time complexity: O(n^2)

Space complexity: O(1)

C++

# Solution2: MergeSort

Time complexity: O(nlogn)

Space complexity: O(n)

C#

# Solution3: Input Property

Input is a permutation of [0, 1, …, N – 1]

Time Complexity: O(n)

Space Complexity: O(1)

Mission News Theme by Compete Themes.