数组题目总结 ---- 田忌赛马

一. 优势洗牌

• 题目链接：https://leetcode.cn/problems/advantage-shuffle/description/

思路和代码：

• 本质上就是两个队列给它排序，我方最大和敌方max打，
  • 打得过，就将我方max加入res当中；
  • 如果打不过，就让我方min打地方的max，将我方min放入res当中。

法一：优先队列法

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
		//设置优先队列，排序的规则是从大到小排列
        PriorityQueue<int[]> maxpq = new PriorityQueue<>(
            (int[] pair1, int[] pair2) ->{
                return pair2[1] - pair1[1];
            }
        );
        //将nums1排序（从小到大）
        Arrays.sort(nums1);

        int left = 0, right = n-1;
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            maxpq.offer(new int[]{i, nums2[i]});
        
        while(!maxpq.isEmpty()){
            int[] pair = maxpq.poll();
            //maxpq 第一个是max，而对于nums1来说，最右边是max
            int i = pair[0], maxval = pair[1];
            if(maxval < nums1[right]){
                res[i] = nums1[right];
                right--;
            }
            else{
                res[i] = nums1[left];
                left++;
            }
               
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

法二：索引排序法

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;

        Integer[] index = new Integer[n];

        for(int i = 0; i < n; i++)
            index[i] = i;
        

        Arrays.sort(nums1);
        //从小到大排序
        Arrays.sort(index, (i, j) -> nums2[i] - nums2[j]);

        int left = 0, right = n-1;
		
		//直接再nums2上更新结果，如果num大放到前面，如果num小，放到最后面去
        for(int num : nums1){
            if(num > nums2[index[left]])
                nums2[index[left++]] = num;
            else
                nums2[index[right--]] = num;
        }
        return nums2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 时间复杂度：O(nlogn)，堆排序的时间，Arrays.sort()底层用的是归并排序，PriorityQueue底层用的是二叉堆来实现的。
• 空间复杂度：O(n)，存储下标用的n个空间。
  参考：https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/tian-ji-sa-7baa4/