Сопряжение чисел (a, b) в массиве таким образом, что a * 2> = b

Question

Я пытаюсь решить парные числа (a, b) в массиве так, чтобы a*2 >=b.Где a и b - числа из входного массива.

Примеры:

input: a[] = {1,2,3,4,5}

output: 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] найден, то add 1, чтобы получить результатповторить для start +1 и end - 1
• иначе повторить для (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));
        }

    }

тесты:

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 <<em> 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, не оставляя шансов сформировать две пары из оставшихся чисел.

Answer 2

Вы можете решить это так:

я. сортировать массив.

II. для каждого числа a найдите крайнюю левую позицию p массива, который содержит> = 2 * b. тогда вы можете посчитать, сколько числа удовлетворены.

Сложность: O (nlogn) + nlogn