东莞网站建设方案服务,iis部署网站项目,怎么做网页个人简介,要建设一个网站需要什么时候开始题目地址#xff1a;https://leetcode.cn/problems/advantage-shuffle/description/
题目描述#xff1a; 给定两个长度相等的数组 nums1 和 nums2#xff0c;nums1 相对于 nums2 的优势可以用满足 nums1[i] nums2[i] 的索引 i 的数目来描述。 返回 nums1 的任意排列https://leetcode.cn/problems/advantage-shuffle/description/
题目描述 给定两个长度相等的数组 nums1 和 nums2nums1 相对于 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] 提示 1 nums1.length 10^5 nums2.length nums1.length 0 nums1[i] ,nums2[i] 10^9 解题思路(典型贪心算法) 田忌赛马的故事大家应该都听说过 田忌和齐王赛马两人的马分上中下三等如果同等级的马对应着比赛田忌赢不了齐王。但是田忌遇到了孙膑 孙膑就教他用自己的下等马对齐王的上等马再用自己的上等马对齐王的中等马最后用自己的中等马对齐王的下等马结果三局两胜田忌赢了。 田忌赛马的核心思路就是打得过就打打不过就拿自己的垃圾和对方的精锐互换。 把nums1当成是田忌的马nums2当成是齐威王的马。 讨论田忌的下等马(nums的最小值) 如果它能比过齐威王的下等马(nums的最小值)那这一分田忌直接拿下 如果它比不过齐威王的下等马则用田忌的下等马比齐威王的上等马(mums2的最大值)。 去掉这两匹马问题变成一个规模更小(n-1)的子问题。重复上述过程即得到了所有马的对应 关系。 代码实现时由于num2不能排序我们可以创建一个下标数组ids,对ids排序即ids[0]对应 nums2中最小值的下标ids[1]对应num2中第二小值的下标。用双指针操作ids,从而知道 每个下标所要对应的nums1的元素也就找到了所要求的nums1的排列。 解题思路来自灵茶山艾府https://leetcode.cn/problems/advantage-shuffle/solutions/1/tian-ji-sai-ma-by-endlesscheng-yxm6/ 代码实现
public class Solution{public int[] advantageCount(int[] nums1, int[] nums2) {//先对nums1进行排序Arrays.sort(nums1);//对muns2排序 但是mums2不能直接排序 需要额外借助一个数据排序int nums2Len nums2.length;int [] ids new int [nums2Len];//记录nums2的下标for(int i 0;in;i){ids[i]i;}//将num2进行排序 注意这里不能直接对nums2排序 转对nums2的下标排序代替nums2的顺序//升序排列 降序也是一个样Arrays.sort(ids,(i,j)-nums2[i]-nums2[j]);//赛马打得过就打打不过就拿自己的垃圾和对方的精锐互换int [] ans new int[nums1.length];int right nums2Len;int left 0;for (int x : nums1) {ans[x nums2[ids[left]] ? ids[left] : ids[right--]] x;}return ans;}
}
