在数组中配对数字(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

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

• 对输入数组进行排序
• 如果发现 [开始]*2> = [结束]然后add 1结果重复 start +1和end - 1
• 否则重复(start + 1, end),(start, end - 1)和 (start + 1, end - 1)

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

    }

测试:

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.数组长度的一半(如果长度为奇数则向下舍入).您可以按照自己喜欢的方式配对数字.对于非负一和b如果一个*2 < b,只是交换一个和b,你将有一个*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中的至少一个,没有机会从剩余的数字形成两对.