給定兩個(gè)大小相等的數(shù)組?A?和?B，A 相對(duì)于 B 的優(yōu)勢(shì)可以用滿(mǎn)足?A[i] > B[i]?的索引 i?的數(shù)目來(lái)描述。

返回?A?的任意排列，使其相對(duì)于 B?的優(yōu)勢(shì)最大化。

?

示例 1：

輸入：A = [2,7,11,15], B = [1,10,4,11]
輸出：[2,11,7,15]
示例 2：

輸入：A = [12,24,8,32], B = [13,25,32,11]
輸出：[24,32,8,12]
?

提示：

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

思路：有點(diǎn)像田忌賽馬的優(yōu)化版

先讓自己最弱的馬和對(duì)面最弱的馬跑一下，如果能贏，那就他兩跑，如果跑不贏，就讓這匹馬和對(duì)面最強(qiáng)的馬賽跑

這道題如何實(shí)現(xiàn)這個(gè)想法呢？

先對(duì)兩個(gè)數(shù)組進(jìn)行排序，但是呢得記錄下b的索引，這樣才知道一會(huì)把馬往哪個(gè)位置放

如果a最小的數(shù)大于等于b最小的數(shù)，則把它放在b最小的數(shù)的索引處。

反之，則把它放在b最大的數(shù)的索引處。

提交的代碼：

class Temp implements Comparable<Temp >{
?? ?int num, index;?
?? ?public Temp(int num, int index) {
?? ??? ?this.index = index;
?? ??? ?this.num = num;
?? ?}
?? ?@Override
?? ?public int compareTo(Temp o) {
?? ??? ?return this.num - o.num;
?? ?}
}
public class Solution {
public static int[] advantageCount(int[] A, int[] B) {
? ? ? ? Arrays.sort(A);
? ? ? ? Temp c[] = new Temp[B.length];
? ? ? ? int i=0,j=A.length-1,k=0;
? ? ? ? int[] d = new int[A.length];
? ? ? ? for(i=0;i<B.length;i++)
? ? ? ? {
? ? ? ? ?? ?c[i] = new Temp(B[i],i);
? ? ? ? }
? ? ? ? Arrays.sort(c);
? ? ? ? i=0;
? ? ? ? while(k<=j)
? ? ? ? {
? ? ? ? ?? ?if(A[i]>c[k].num)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?d[c[k].index] = A[i];
? ? ? ? ?? ??? ?i++;
? ? ? ? ?? ??? ?k++;
? ? ? ? ?? ?}
? ? ? ? ?? ?else
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?d[c[j].index] = A[i];
? ? ? ? ?? ??? ?i++;
? ? ? ? ?? ??? ?j--;
? ? ? ? ?? ?}
? ? ? ? }
? ? ? ? return d;
? ? }
}

完整的代碼：

import java.util.Arrays;
class Temp implements Comparable<Temp >{
?? ?int num, index;?
?? ?public Temp(int num, int index) {
?? ??? ?this.index = index;
?? ??? ?this.num = num;
?? ?}
?? ?@Override
?? ?public int compareTo(Temp o) {
?? ??? ?return this.num - o.num;
?? ?}
}
public class Solution870 {
public static int[] advantageCount(int[] A, int[] B) {
? ? ? ? Arrays.sort(A);
? ? ? ? Temp c[] = new Temp[B.length];
? ? ? ? int i=0,j=A.length-1,k=0;
? ? ? ? int[] d = new int[A.length];
? ? ? ? for(i=0;i<B.length;i++)
? ? ? ? {
? ? ? ? ?? ?c[i] = new Temp(B[i],i);
? ? ? ? }
? ? ? ? Arrays.sort(c);
? ? ? ? i=0;
? ? ? ? while(k<=j)
? ? ? ? {
? ? ? ? ?? ?if(A[i]>=c[k].num)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?d[c[k].index] = A[i];
? ? ? ? ?? ??? ?i++;
? ? ? ? ?? ??? ?k++;
? ? ? ? ?? ?}
? ? ? ? ?? ?else
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?d[c[j].index] = A[i];
? ? ? ? ?? ??? ?i++;
? ? ? ? ?? ??? ?j--;
? ? ? ? ?? ?}
? ? ? ? }
? ? ? ? return d;
? ? }
public static void main(String[] args)
{
?? ?int a[] = {12,24,8,32};
?? ?int b[] = {13,25,32,11};
?? ?int c[] = new int[a.length];
?? ?c = advantageCount(a,b);
?? ?for(int i = 0;i<c.length;i++)
?? ?{
?? ??? ?System.out.println(c[i]+" ");
?? ?}
}

}
?

總結(jié)

以上是生活随笔為你收集整理的Leetcode--870. 优势洗牌的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。