服务器上怎做网站网站只收录无权重

服务器上怎做网站,网站只收录无权重,制作公司网页,o2o模式成功案例贪心双指针求解优势洗牌问题#xff08;C 实现#xff09; 题目描述 给定两个长度相等的数组 nums1 和 nums2#xff0c;定义 nums1 相对于 nums2 的优势为满足 nums1[i] nums2[i] 的索引 i 的数量。要求返回 nums1 的任意一个排列#xff0c;使得该排列相对于 nums2 …贪心双指针求解优势洗牌问题C 实现题目描述给定两个长度相等的数组nums1和nums2定义nums1相对于nums2的优势为满足nums1[i] nums2[i]的索引i的数量。要求返回nums1的任意一个排列使得该排列相对于nums2的优势最大化。问题分析结合题目要求和数据特征我们可以先梳理核心约束与解题思路两个数组长度相同排列后元素需按索引一一对应匹配目标是最大化满足nums1[i] nums2[i]的索引数量本质是用最优的匹配策略实现收益最大化直接暴力枚举所有排列会产生极高的时间复杂度无法高效处理较大数据量因此需要选择更优的算法方案。结合问题特征贪心算法双指针是适配该场景的最优解贪心策略用于保证每一步选择都能获取当前最优收益双指针用于高效遍历匹配元素整体算法可以在线性遍历结合排序的基础上完成计算。算法思路核心策略采用贪心匹配原则用nums1中最小的可用大数去匹配nums2中对应元素无法满足大小关系时用nums1中最小的数去填充最大化有效匹配数量的同时减少优质元素的浪费。具体步骤数组预处理对nums1执行升序排序方便通过双指针快速获取当前最大/最小可用元素为nums2构建(值, 原索引)的键值对数组再对该数组执行升序排序。保留原索引是为了保证最终结果能对应到题目要求的原始位置。双指针初始化定义左指针left指向排序后nums1的起始位置最小值右指针right指向排序后nums1的末尾位置最大值。逆序遍历匹配从大到小遍历处理后的nums2数组依次判断当前元素若nums1的当前最大值大于nums2的当前元素将该最大值填入结果数组的对应原始索引右指针左移若不满足大小关系说明当前最大元素也无法形成优势改用nums1的当前最小值填充左指针右移。输出结果遍历完成后结果数组即为满足条件的nums1最优排列。C 实现代码#includevector#includealgorithmusingnamespacestd;classSolution{public:vectorintadvantageCount(vectorintnums1,vectorintnums2){// 获取数组长度intnnums1.size();// 初始化结果数组长度与输入数组一致vectorintres(n,0);// 存储nums2的(值, 原索引)对保留原始位置信息vectorpairint,intnums2_temp;for(inti0;in;i){nums2_temp.emplace_back(nums2[i],i);}// 对nums1升序排序sort(nums1.begin(),nums1.end());// 对nums2的键值对数组按值升序排序sort(nums2_temp.begin(),nums2_temp.end());// 双指针初始化left指向nums1最小值right指向nums1最大值intleft0;intrightn-1;// 逆序遍历排序后的nums2_temp从大元素开始匹配for(intin-1;i0;--i){intvalnums2_temp[i].first;// nums2当前元素值intindexnums2_temp[i].second;// 该元素在原数组中的索引// 贪心选择能用大值匹配就用大值否则用小值填充if(valnums1[right]){res[index]nums1[right];--right;}else{res[index]nums1[left];left;}}returnres;}};复杂度分析时间复杂度算法主要耗时操作为排序操作nums1排序的时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)nums2键值对数组排序的时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)后续双指针遍历为线性操作时间复杂度为O(n)O(n)O(n)。整体时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)在数据量较大时仍能保持高效运行。空间复杂度额外开辟了存储nums2键值对的数组nums2_temp和结果数组res两者空间开销均为O(n)O(n)O(n)排序过程中递归调用栈的空间开销为O(log⁡n)O(\log n)O(logn)可忽略不计。整体空间复杂度为O(n)O(n)O(n)属于线性空间开销。算法验证与适用场景该算法通过贪心策略保证了每一步匹配的最优性双指针遍历避免了重复判断能够稳定得到优势最大化的排列。适用于题目给定的所有常规场景无特殊数据边界限制在力扣对应题目中可通过全部测试用例。总结本题核心解法为贪心算法双指针通过排序预处理和逆序匹配实现最优解算法时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)空间复杂度为O(n)O(n)O(n)兼顾了时间效率与实现简洁性保留原数组索引是解题关键确保排列结果能对应到题目要求的原始位置。