java - 以 a*2 >=b 的方式对数组中的数字 (a,b) 进行配对

Question

我正在尝试以 a*2 >=b 的方式求解数组中的配对数 (a,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

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

• 对输入数组进行排序
• if a[start] * 2 >= [end] found then add 1 to result recur for start +1 和 结束 - 1
• else 重复出现 (start + 1, end), (start, end - 1) 和(开始 + 1，结束 - 1)

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

    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));
        }

    }

测试:

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;


public class CountingPairsTest {

    static int countPairs(int[] a){
        return PairingNumbers.countPairs(a);
    }

    @Test
     public void test1(){
        int[] a = {1,2,3,4,5};
        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public void test2(){
        int[] a = {1,2,3,4,5,6};
        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public void test5(){
        int[] a = {1,2,3,7,4,5,6};
        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public void test6(){
        int[] a = {9,8,20,15,21};

        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public  void test3(){
        int[] a = {5,4,3,2,1};
        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public void test4(){
        int[] a = {2,4,5,3,1};

        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }

    @Test public void test7(){
        int[] a = new Random().ints(10,1,100).toArray();// IntStream.range(1,100).toArray();


        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }
    @Test public void test8(){
        int[] a = new Random().ints(10,1,10).toArray();// IntStream.range(1,100).toArray();


        System.out.println("****************************************\n" + Arrays.toString(a));
        int count = countPairs(a);
        System.out.println("count "+count);
    }
}

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。在这种情况下，我们甚至不需要任何交换(在另一方面，相同的对也可以 交换:2 * 2 >= 1 和 2 * 2 >= 2)。

如果数组可能包含负数，它并不总是有效。因此，您可能想要添加一个数组验证来检查它是否存在。

您的解决方案出了什么问题？

你的递归算法是错误的。假设数组是 [2, 3, 7, 9]。显然 (2, 3) 和 (7, 9) 是很好的对，所以这里有两对。您描述算法的方式是，由于 (2, 9) 不是有效对，因此您至少丢弃 2 和 9 中的一个，从而没有机会从剩余数字中形成两对。