将数组中的数字 (a,b) 配对，使得 a*2 >=b

Question

我正在尝试以这样的方式解决数组中的配对数字（a，b）a*2 >=b。其中 a 和 b 是输入数组中的数字。

例子：

输入：a[]  = {1,2,3,4,5}

输出：2

解释：

• 我们可以将 1 与 3 配对

• 2 与 4 或 5

输入：a[]  = {4,3,2,1,5}

输出：2

解释：

• 我们可以将 1 与 3 配对

• 2 与 4 或 5

输入：a[]  = {4,3,2,1,5,6}

输出：3

解释：

• 我们可以将 5 与 1 配对

• 2 与 4

• 3 与 6

我尝试使用如下递归来解决问题，但这并没有给出任何正确的结果。任何帮助，将不胜感激。

• 对输入数组进行排序

• 如果a[start] * 2 >= [end] found then add 1to result recur for start +1andend - 1

• else为(start + 1, end),(start, end - 1)和 (start + 1, end - 1)

a[start]想法与数组中的剩余元素匹配并获得最大结果。

   public static int countPairs(int[] a){

       Arrays.sort(a);

       return countPairs(a,a.length,0,a.length-1);

    }

    public static int countPairs(int[] a, int n, int start, int end){

        if(end == start){

            return 0;

        }

        if(start >= n || end < 0){

            return 0;

        }

         System.out.print("matching start: "+start + " and end "+end+"   ");System.out.println("matching "+a[start] + " and "+a[end]);

        if(a[start] < a[end] && a[start] * 2 >= a[end]  ){

            int res = countPairs(a,n,start+1,end-1) +1;

             //System.out.print("inside if matching start: "+start + " and end "+end+"   ");System.out.println("matching "+a[start] + " and "+a[end] + " count is "+res);

            return res;

        }

        else{

            return max(countPairs(a,n,start+1,end) ,

                    countPairs(a,n,start,end - 1),countPairs(a,n,start+1,end - 1));

        }

    }

Answer 1

我建议答案是a.length / 2。数组长度的一半（如果长度为奇数，则向下舍入）。您可以以任何您喜欢的方式配对数字。对于非负a和b如果a&nbsp;* 2 <&nbsp;b，只需交换a和b，您将得到a&nbsp;* 2 >=&nbsp;b。因此，由于配对需要两个数字，因此您始终可以精确地形成与数组长度的一半一样多的配对。示例（来自评论）：[1, 2, 2, 2]。长度是4，长度的一半是2，所以应该有2对。让我们检查一下：(1, 2) 是一个不错的对，因为 1 * 2 >= 2。(2, 2) 是另一个不错的对，因为 2 * 2 >= 2。在这种情况下，我们甚至不需要任何交换 (on另一方面，相同的对也可以用于交换：2 * 2 >= 1 和 2 * 2 >= 2)。如果数组可能包含负数，它并不总是有效。因此，您可能想要添加一个数组验证来检查它是否没有。您的解决方案出了什么问题？您的递归算法是错误的。假设数组是 [2, 3, 7, 9]。显然 (2, 3) 和 (7, 9) 是很好的对，所以这里有两对。你描述你的算法的方式，因为 (2, 9) 不是一个有效的对，你丢弃 2 和 9 中的至少一个，没有机会从剩余的数字中形成两对。

Answer 2

你可以这样解决它：一世。排序数组。ii.&nbsp;对于每个数字a找到包含 >= 2*b 的数组的最左边位置p 。然后你可以数出有多少满意。复杂度：O(nlogn)+nlogn