AlgoPressAppearance
题目描述
https://leetcode.cn/problems/advantage-shuffle
给定两个大小相等的数组 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 <= 10^5
- nums2.length == nums1.length
- 0 <= nums1[i], nums2[i] <= 10^9
思路
田忌赛马，如果我能赢你的，用最小的数去赢你，如果不能赢你的，则用最小的数去输。
参考代码
csharp
public class Solution {
public int[] AdvantageCount(int[] nums1, int[] nums2) {
//思路，找出大于对方的最小的数，否则就找出当前最小的数
int minIndex ;
int overMinIndex ;
for(int i=0; i<nums1.Length; i++){
int v = nums2[i];
//找出从 num 开始最小的数
minIndex = i;
overMinIndex = -1;
for(int j=i; j<nums1.Length; j++){
//最小数
if(nums1[j] < nums1[minIndex]){
minIndex = j;
}
//能赢对方的最小数
if(nums1[j] > nums2[i]){
if(overMinIndex == -1){
overMinIndex = j;
}
else if(nums1[j] < nums1[overMinIndex]){
overMinIndex = j;
}
}
}
//开始替换
int swapIndex = overMinIndex != -1 ? overMinIndex : minIndex;
int temp = nums1[i];
nums1[i] = nums1[swapIndex];
nums1[swapIndex] = temp;
}
return nums1;
}
}
参考代码2：优化超时问题
将 nums1 先排序，然后根据同样的原理(能赢就选赢的中最小的，输掉就选自己最小的)，选择合适的数字到对应位置。
csharp
public class Solution {
public int[] AdvantageCount(int[] nums1, int[] nums2) {
int n = nums1.Length;
Array.Sort(nums1);
int minIndex = 0;
int[] nums = new int[n];
for(int i=0; i<n; i++){
bool win = false;
//找到最小的能赢的数
for(int j=0; j<nums1.Length; j++){
if(nums1[j] > nums2[i]){
nums[i] = nums1[j];
nums1[j] = -1;
win = true;
break;
}
}
if(!win){
while(nums1[minIndex] == -1){
minIndex++;
}
nums[i] = nums1[minIndex];
nums1[minIndex] = -1;
minIndex++;
}
}
return nums;
}
}
复习：20220711
csharp
public class Solution {
public int[] AdvantageCount(int[] nums1, int[] nums2) {
int n = nums1.Length;
Array.Sort(nums1); //排序第一个数组
//第二个数组排序并且记录索引
int[][] n2 = new int[n][];
for(int i=0; i<n; i++){
n2[i] = new int[]{nums2[i],i};
}
Array.Sort(n2,(a,b)=>{
return a[0].CompareTo(b[0]);
});
int[] result = new int[n];
int left = 0;
int right = n-1;
for(int i=0; i<n; i++){
if(nums1[i] > n2[left][0]){
result[n2[left][1]] = nums1[i]; //如果小的数能赢得对方，则直接输出
left++;
}
else{
result[n2[right][1]] = nums1[i]; //如果小的数不能赢得对方，则和对方最大的比
right--;
}
}
return result;
}
}