保持x有序时，如何调整B数组使各索引y值均大于A数组对应值？

核心思路 #

不用枚举所有排列，用贪心策略就能高效解决问题——核心是在每个x值对应的分组内，用最小的能满足条件的B.y去匹配A.y，避免浪费较大的B.y资源，确保组内所有元素都能找到对应匹配。

具体步骤 #

1. 分组校验

   • 先把A和B按x值分组，确保两组的x值序列完全一致（每个x出现的次数、顺序都必须相同）。比如A的x序列是[2,2,3]，B的x序列也得是[2,2,3]，否则直接判定为无法满足需求。

2. 组内排序与匹配
   对每个x对应的A子数组和B子数组：

   • 提取A子数组的所有y值，按升序排序；
   • 提取B子数组的所有y值，也按升序排序；
   • 用双指针法逐一匹配：
     • 初始化指针i（指向A排序后的y数组）、j（指向B排序后的y数组）；
     • 遍历每个A.y：
       • 如果当前B.y[j] > A.y[i]，则匹配成功，同时移动i和j；
       • 否则，移动j寻找下一个更大的B.y；
     • 如果遍历完A的所有y后，i没有走到数组末尾（存在A.y找不到对应的B.y），则整体判定为失败。

3. 全局判定
   所有x分组都匹配成功时，说明可以调整B的同x元素位置满足需求；只要有一个分组匹配失败，直接返回不可行。

示例说明 #

比如：

• A中x=2的子数组y为[1,3]，B中x=2的子数组y为[4,2]
• 排序后A.y为[1,3]，B.y为[2,4]
• 双指针匹配：1→2（满足），3→4（满足），分组匹配成功，整体可行。

再比如：

• A中x=2的子数组y为[2,3]，B中x=2的子数组y为[1,4]
• 排序后A.y为[2,3]，B.y为[1,4]
• 匹配第一个A.y=2时，B.y[0]=1不满足，移动j到1，B.y[1]=4满足，此时i=1，j=2（超出B数组范围）；第二个A.y=3找不到对应B.y，分组匹配失败，整体不可行。

复杂度分析 #

• 分组操作：O(n)，n为数组长度；
• 组内排序：总复杂度O(n log k)，k为各分组的元素数量，整体等价于O(n log n)；
• 双指针匹配：O(n)；
• 整体复杂度远低于暴力枚举排列的O(n!)，适合处理大规模数组。

内容的提问来源于stack exchange，提问作者tygutowski