求解满足2*min(arr[i],arr[j])≤max(arr[i],arr[j])的最大不重复配对数

给定一个长度为n的数字列表，需找出满足2 * min(arr[i], arr[j]) ≤ max(arr[i], arr[j])的最大配对数量，要求每个索引仅能使用一次（已配对的索引不可重复使用）。

约束条件 #

• n的取值范围为1到1e5（原描述笔误修正）
• 数组元素取值范围为1到10^9

示例 #

示例1 #

输入：arr = [2, 5, 7, 6, 9, 8 , 4 , 2]
结果：3
解释：排序后数组为[2,2,4,5,6,7,8,9]，最优配对如(2,5)、(2,7)、(4,9)，共3对。若将2与4配对，会浪费4无法和8/9配对，导致总配对数减少。

示例2 #

输入：arr = [2,1,2,4,1,4,1]
结果：3
解释：排序后数组为[1,1,1,2,2,4,4]，最优配对如(1,2)、(1,4)、(1,4)，共3对。

你的代码问题分析 #

你用TreeMap实现的思路错误在于贪心策略方向：降序排序后尝试用当前元素找更大的满足条件的元素，这会浪费大元素（比如示例2中用2配对4，导致1无法找到足够的配对对象），最终得到更少的配对数。

正确解法：升序排序+双指针贪心 #

核心思路是：升序排序后，用前半部分的小元素去配对后半部分的大元素，尽可能让每个小元素都找到能满足条件的最小大元素，避免浪费大元素，从而最大化配对数量。

具体步骤 #

1. 将数组升序排序。
2. 初始化两个指针：left从数组起始位置（0）开始，right从数组中间位置（n//2）开始，配对计数count=0。
3. 遍历数组：
   • 若2 * arr[left] ≤ arr[right]，说明当前小元素可以和这个大元素配对，计数加1，同时两个指针都右移。
   • 若不满足条件，说明当前大元素太小，无法和当前小元素配对，将right右移寻找更大的元素。
4. 遍历结束后，count即为最大配对数。

Java代码实现 #

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 5, 7, 6, 9, 8, 4, 2))); // 输出3
        System.out.println(solve(Arrays.asList(2, 1, 2, 4, 1, 4, 1))); // 输出3
    }

    static int solve(List<Integer> arr) {
        Collections.sort(arr); // 升序排序
        int n = arr.size();
        int left = 0;
        int right = n / 2;
        int count = 0;

        while (right < n && left < n / 2) {
            if (2 * arr.get(left) <= arr.get(right)) {
                count++;
                left++;
                right++;
            } else {
                right++;
            }
        }
        return count;
    }
}

解法原理 #

升序排序后，前半部分的元素是较小的一批，后半部分是较大的一批。用小元素优先配对合适的大元素，能保证大元素不会被过早消耗在不需要它们的配对中（比如用大元素配对中等元素，而不是留给更小的元素），从而最大化总配对数。这种策略的时间复杂度为O(n log n)（主要来自排序），符合n=1e5的性能要求。

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