将数组中的数字 (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 与 43 与 6我尝试使用如下递归来解决问题，但这并没有给出任何正确的结果。任何帮助，将不胜感激。对输入数组进行排序如果a[start] * 2 >= [end] found then add 1to result recur for start +1andend - 1else为(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 * 2 < b，只需交换a和b，您将得到a * 2 >= 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. 对于每个数字a找到包含 >= 2*b 的数组的最左边位置p 。然后你可以数出有多少满意。

复杂度：O(nlogn)+nlogn