算法题 优势洗牌

优势洗牌

问题描述

给定两个长度相等的数组nums1和nums2，你需要对nums1进行重排列，使得nums1相对于nums2的优势最大化。

优势定义：对于索引i，如果nums1[i] > nums2[i]，则称nums1在位置i上具有优势。

目标是返回一个nums1的排列，使得优势的总数最大。

示例：

输入:nums1=[2,7,11,15],nums2=[1,10,4,11]输出:[2,11,7,15]解释:-nums1[0]=2>nums2[0]=1-nums1[1]=11>nums2[1]=10-nums1[2]=7>nums2[2]=4-nums1[3]=15>nums2[3]=11优势总数为4，是最大可能值。 输入:nums1=[12,24,8,32],nums2=[13,25,32,11]输出:[24,32,8,12]解释:-24>13-32>25-8<=32-12>11优势总数为3。

算法思路

贪心策略 + 双指针（田忌赛马）：

1. 核心思想（田忌赛马）：

   • 用nums1中刚好能赢nums2中每个元素的最小值
   • 如果nums1中没有能赢nums2[i]的元素，就用最小的元素去输

2. 为什么这样最优：

   • 如果最大值能赢当前nums2元素，那么用最大值是最优的（保留较小的值应对更小的对手）
   • 如果最大值都不能赢，说明任何元素都不能赢，用最小值输掉是最优的（保留大值应对更大的对手）

代码实现

方法一：贪心 + 双指针

importjava.util.*;classSolution{/** * 优势洗牌 - 贪心算法 * * @param nums1 数组1，可以重排列 * @param nums2 数组2，固定不变 * @return nums1的一个排列，使得优势最大化 * * 算法思路（田忌赛马）： * 1. 对nums1排序 * 2. 对nums2的索引按值排序（保存原始位置） * 3. 双指针：left指向最小值，right指向最大值 * 4. 对于每个nums2元素（从小到大处理）： * - 如果nums1[right] > nums2[i]：用最大值赢 * - 否则：用最小值输 */publicint[]advantageCount(int[]nums1,int[]nums2){intn=nums1.length;// 对nums1进行排序Arrays.sort(nums1);// 创建nums2的索引数组，并按nums2的值排序Integer[]indices=newInteger[n];for(inti=0;i<n;i++){indices[i]=i;}// 按nums2的值升序排序索引Arrays.sort(indices,(i,j)->Integer.compare(nums2[i],nums2[j]));// 结果数组int[]result=newint[n];// 双指针：left指向nums1最小值，right指向nums1最大值intleft=0,right=n-1;// 从nums2最大的元素开始处理（逆序遍历排序后的索引）// 可以优先处理最难赢的元素for(inti=n-1;i>=0;i--){intoriginalIndex=indices[i];// nums2中当前元素的原始位置intnums2Value=nums2[originalIndex];// 如果nums1的最大值能赢nums2的当前最大值if(nums1[right]>nums2Value){// 用最大值赢result[originalIndex]=nums1[right];right--;}else{// 用最小值输（最大值都赢不了，说明所有值都赢不了）result[originalIndex]=nums1[left];left++;}}returnresult;}}

方法二：贪心 + 优先队列

importjava.util.*;classSolution{/** * 使用优先队列 * * @param nums1 数组1 * @param nums2 数组2 * @return 优势最大化的排列 */publicint[]advantageCount(int[]nums1,int[]nums2){intn=nums1.length;// 对nums1排序Arrays.sort(nums1);// 创建最大堆，存储nums2的值和索引PriorityQueue<int[]>maxHeap=newPriorityQueue<>((a,b)->b[0]-a[0]);for(inti=0;i<n;i++){maxHeap.offer(newint[]{nums2[i],i});}int[]result=newint[n];intleft=0,right=n-1;// 从nums2的最大值开始处理while(!maxHeap.isEmpty()){int[]current=maxHeap.poll();intnums2Value=current[0];intoriginalIndex=current[1];if(nums1[right]>nums2Value){result[originalIndex]=nums1[right];right--;}else{result[originalIndex]=nums1[left];left++;}}returnresult;}}

算法分析

• 时间复杂度：O(n log n)

  • 排序nums1：O(n log n)
  • 排序nums2索引：O(n log n)
  • 双指针遍历：O(n)
  • 总体：O(n log n)

• 空间复杂度：O(n)

  • 存储索引数组：O(n)
  • 结果数组：O(n)
  • 其他变量：O(1)

算法过程

1：nums1 = [2,7,11,15], nums2 = [1,10,4,11]

步骤：

1. nums1排序后：[2,7,11,15]
2. nums2索引按值降序排序：[3(11), 1(10), 2(4), 0(1)]
3. 双指针：min=0, max=3

过程：

• 处理nums2[3]=11：nums1[3]=15 > 11→ 用15赢，result[3]=15，max=2
• 处理nums2[1]=10：nums1[2]=11 > 10→ 用11赢，result[1]=11，max=1
• 处理nums2[2]=4：nums1[1]=7 > 4→ 用7赢，result[2]=7，max=0
• 处理nums2[0]=1：nums1[0]=2 > 1→ 用2赢，result[0]=2，max=-1

结果：[2,11,7,15]，优势数=4

2：nums1 = [12,24,8,32], nums2 = [13,25,32,11]

步骤：

1. nums1排序后：[8,12,24,32]
2. nums2索引按值降序排序：[2(32), 1(25), 0(13), 3(11)]
3. 双指针：min=0, max=3

过程：

• 处理nums2[2]=32：nums1[3]=32 <= 32→ 用最小值8输，result[2]=8，min=1
• 处理nums2[1]=25：nums1[3]=32 > 25→ 用32赢，result[1]=32，max=2
• 处理nums2[0]=13：nums1[2]=24 > 13→ 用24赢，result[0]=24，max=1
• 处理nums2[3]=11：nums1[1]=12 > 11→ 用12赢，result[3]=12，max=0

结果：[24,32,8,12]，优势数=3

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：完全优势int[]nums1_1={2,7,11,15};int[]nums2_1={1,10,4,11};int[]result1=solution.advantageCount(nums1_1,nums2_1);System.out.println("Test 1: "+Arrays.toString(result1));// 期望: [2,11,7,15] 或其他优势数为4的排列// 测试用例2：部分优势int[]nums1_2={12,24,8,32};int[]nums2_2={13,25,32,11};int[]result2=solution.advantageCount(nums1_2,nums2_2);System.out.println("Test 2: "+Arrays.toString(result2));// 期望: [24,32,8,12] 或其他优势数为3的排列// 测试用例3：无法获得优势int[]nums1_3={1,2,3};int[]nums2_3={4,5,6};int[]result3=solution.advantageCount(nums1_3,nums2_3);System.out.println("Test 3: "+Arrays.toString(result3));// 期望: 任意排列，优势数为0// 测试用例4：相等元素int[]nums1_4={5,5,5};int[]nums2_4={5,5,5};int[]result4=solution.advantageCount(nums1_4,nums2_4);System.out.println("Test 4: "+Arrays.toString(result4));// 期望: [5,5,5]，优势数为0// 测试用例5：单元素int[]nums1_5={1};int[]nums2_5={2};int[]result5=solution.advantageCount(nums1_5,nums2_5);System.out.println("Test 5: "+Arrays.toString(result5));// 期望: [1]// 测试用例6：大数测试int[]nums1_6={10,20,30,40,50};int[]nums2_6={5,15,25,35,45};int[]result6=solution.advantageCount(nums1_6,nums2_6);System.out.println("Test 6: "+Arrays.toString(result6));// 期望: 优势数为5的排列// 测试用例7：重复元素int[]nums1_7={2,0,4,1,2};int[]nums2_7={1,3,0,0,2};int[]result7=solution.advantageCount(nums1_7,nums2_7);System.out.println("Test 7: "+Arrays.toString(result7));}// 计算优势数publicstaticintcountAdvantage(int[]a,int[]b){intcount=0;for(inti=0;i<a.length;i++){if(a[i]>b[i])count++;}returncount;}}

关键点

1. 田忌赛马：

   • 用最弱的马对最强的马（如果赢不了）
   • 用刚好能赢的马对对手的马（如果能赢）

2. 贪心选择：

   • 如果最大值能赢当前最大值，那么用最大值是最优的
   • 如果最大值不能赢，那么任何值都不能赢，用最小值是最优的

3. 索引排序：

   • 需要保持nums2元素的原始位置信息
   • 按值排序索引可以按特定顺序处理元素

4. 处理顺序：

   • 从nums2的最大值开始处理
   • 可以优先处理最难赢的元素，做出最优决策

常见问题

1. 为什么要从最大值开始处理？

   • 最大值是最难赢的对手
   • 优先处理最难的情况可以避免浪费大值在容易赢的对手上

2. 为什么不能从小到大处理？

   • 从小到大处理可能导致：用大值赢了小对手，结果面对大对手时没有足够的大值
   • 从大到小处理确保了资源的最优分配