870. 优势洗牌(难度:中等)

2023-03-05  本文已影响0人  一直流浪

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

题目描述:

给定两个大小相等的数组 nums1nums2nums1 相对于 nums2优势可以用满足 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]

提示:

解法:贪心算法

这道题的意思,总结起来就一句话,让nums1重新排序,然后在相同索引下尽可能大于nums2的元素。也就是田忌赛马,将两个数组都先进行升序排序,然后依次使用下标i去遍历nums1,使用left 和 right 分别表示nums2数组的最左边下标和最右边下标。

使用nums1最小的元素去和nums2最小元素比较,

就这样依次移动下标 i 和 left、right直到遍历结束。

代码:

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums2.length;
        Integer[] index1 = new Integer[n];
        Integer[] index2 = new Integer[n];
        for (int i = 0; i < n; i++) {
            index1[i] = i;
            index2[i] = i;
        }
        Arrays.sort(index1, Comparator.comparingInt(a -> nums1[a]));
        Arrays.sort(index2, Comparator.comparingInt(a -> nums2[a]));

        int[] ans = new int[n];
        int left = 0, reight = n - 1;
        for (int i = 0; i < n; i++) {
            if (nums1[index1[i]] > nums2[index2[left]]) {
                ans[index2[left]] = nums1[index1[i]];
                left++;
            } else {
                ans[index2[reight]] = nums1[index1[i]];
                reight--;
            }
        }
        return ans;
    }
}
上一篇下一篇

猜你喜欢

热点阅读