LeetCode870 优势洗牌 田忌赛马问题

LeetCode870 优势洗牌

1. 思路分析

   1. 本题相当于田忌赛马，尽可能多的让nums1[i] > nums2[i]

   2. 策略：将nums1升序排列，将nums2降序排列(因为nums2中元素的顺序不能改变，计算结果的顺序依赖nums2的顺序，因此利用PriorityQueue放入int[]{i, nums2[i]})，

      然后一一对比：如果nums1[right]大于maxval，即nums1的最大值大于了nums2的最大值，那么直接写入res数组中对应索引；否则，将nums1的最小值写入res数组中对应索引

   3. 使用双指针技巧中的左右指针left, right，分别指向nums1的最小值和最大值

   4. 示意图

2. 代码实现

   class Solution {
       public int[] advantageCount(int[] nums1, int[] nums2) {
           //大顶堆，将nums2降序排列
           PriorityQueue maxpq = new PriorityQueue<>((int[] pair1, int[] pair2) -> pair2[1] - pair1[1]);
           for (int i = 0; i < nums2.length; i++) {
               //存入索引，以及元素值
               maxpq.offer(new int[]{i, nums2[i]});
           }
           //将nums1升序排列
           Arrays.sort(nums1);
   
           //nums1的左右指针，分别指向最大值和最小值
           int left = 0;
           int right = nums1.length - 1;
           //结果数组
           int[] res = new int[nums1.length];
           for (int i = 0; i < nums1.length; i++) {
               int[] max = maxpq.poll();
               int index = max[0];
               int maxval = max[1];
               //如果nums1最大值大于nums2的最大值，则直接将nums1[right]放入对应索引
               if (nums1[right] > maxval) {
                   res[index] = nums1[right];
                   right--;
               }else {
                   //否则使用最小值放入对应索引
                   res[index] = nums1[left];
                   left++;
               }
           }
           return res;
       }
   }