java - Find unique pairs - Stack Overflow

admin管理员组

文章数量:1122832

There is a list of numbers of size n, find the maximum count of the number of pairs such that it follows the below pattern:

2 * minimum(arr[i],arr[j]) <= maximum (arr[i], arr[j]), where [i,j] in range (0 to n)

The selected indices should be unique, it means if an index say 2 is used to form a pair say (2,5), we should not use the same index 2 to form another pair (2,7).

Example:

arr = [2, 5, 7, 6, 9, 8 , 4 , 2]
result = 3

Explanation:

Sort input = [2,2,4,5,6,7,8,9]
All possible pairs that can be formed are:
2 can form pairs with [4,5,6,7,8,9]
4 can form pairs with [8,9]
For 5, there is no matching pair that satisfies the condition.

We cannot pick the pair (2,4) because if 4 is already used we cannot form new pairs like (4,8) or (4,9)

Finally, we can form 3 maximum counts of pairs using distinct indices, One such possible pairs are (2,5), (7, 2), and (9, 4), so the answer is 3

Example:

arr = [2,1,2,4,1,4,1]
result = 3

Explanation:

Pairs are (2,1), (4,1), and (2,4), so the answer is 3

Constraints:

• n is in the range 1 to n^5
• each input item,is in range 1 to 10^9

I tried solving this using a TreeMap:

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 5, 7, 6, 9, 8 , 4 , 2)));//3
        System.out.println(solve(Arrays.asList(2,1,2,4,1,4,1)));//3
    }
    
    static int solve(List<Integer> arr) {
        arr.sort(Comparator.reverseOrder());
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int e : arr) map.put(e, map.getOrDefault(e,0)+1);
        int result = 0;
        for(int e : arr) {
            int min = 2 * e;
            if(map.get(e) == null) continue;
            Integer key = map.ceilingKey(min);
            if(key != null) {
                map.put(e,map.get(e)-1);
                if(map.get(e) <=0)map.remove(e);
                
                map.put(key,map.get(key)-1);
                if(map.get(key) <=0)map.remove(key);
                result++;
            }
        }
        return result;
    }
}

But for 2nd test case arr = [2,1,2,4,1,4,1], I am creating pairs in my code as (2,4), (2,4), so it is returning 2 instead of 3.

I tried greedy and 2 pointer approach but both are not working.

What is the correct approach for this problem?

There is a list of numbers of size n, find the maximum count of the number of pairs such that it follows the below pattern:

2 * minimum(arr[i],arr[j]) <= maximum (arr[i], arr[j]), where [i,j] in range (0 to n)

The selected indices should be unique, it means if an index say 2 is used to form a pair say (2,5), we should not use the same index 2 to form another pair (2,7).

Example:

arr = [2, 5, 7, 6, 9, 8 , 4 , 2]
result = 3

Explanation:

Sort input = [2,2,4,5,6,7,8,9]
All possible pairs that can be formed are:
2 can form pairs with [4,5,6,7,8,9]
4 can form pairs with [8,9]
For 5, there is no matching pair that satisfies the condition.

We cannot pick the pair (2,4) because if 4 is already used we cannot form new pairs like (4,8) or (4,9)

Finally, we can form 3 maximum counts of pairs using distinct indices, One such possible pairs are (2,5), (7, 2), and (9, 4), so the answer is 3

Example:

arr = [2,1,2,4,1,4,1]
result = 3

Explanation:

Pairs are (2,1), (4,1), and (2,4), so the answer is 3

Constraints:

• n is in the range 1 to n^5
• each input item,is in range 1 to 10^9

I tried solving this using a TreeMap:

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 5, 7, 6, 9, 8 , 4 , 2)));//3
        System.out.println(solve(Arrays.asList(2,1,2,4,1,4,1)));//3
    }
    
    static int solve(List<Integer> arr) {
        arr.sort(Comparator.reverseOrder());
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int e : arr) map.put(e, map.getOrDefault(e,0)+1);
        int result = 0;
        for(int e : arr) {
            int min = 2 * e;
            if(map.get(e) == null) continue;
            Integer key = map.ceilingKey(min);
            if(key != null) {
                map.put(e,map.get(e)-1);
                if(map.get(e) <=0)map.remove(e);
                
                map.put(key,map.get(key)-1);
                if(map.get(key) <=0)map.remove(key);
                result++;
            }
        }
        return result;
    }
}

But for 2nd test case arr = [2,1,2,4,1,4,1], I am creating pairs in my code as (2,4), (2,4), so it is returning 2 instead of 3.

I tried greedy and 2 pointer approach but both are not working.

What is the correct approach for this problem?

• java
• algorithm

Share Improve this question Follow edited Nov 26, 2024 at 15:24 CodeCrusader asked Nov 22, 2024 at 21:23 CodeCrusaderCodeCrusader 15511 silver badge1010 bronze badges 11

• The best I can think of at the moment is just throwing a maximum matching algorithm at the problem, like the blossom algorithm - this problem is a special case of maximum matching. – user2357112 Commented Nov 22, 2024 at 21:46
• 1 If your condition is 2 * minimum(arr[i],arr[j]) <= maximum (arr[i], arr[j]), where [i,j] in range (0 to n). Then why (2,6) is not part of your first example answer? @CodeCrusader – ArtBindu Commented Nov 23, 2024 at 0:57
• 2 What is your criterion for the "correct" approach? FWIW, any code that produces the right answers (for all valid inputs) in a finite time is ... in a sense ... a correct solution. There are many such solutions possible. Indeed, any of your 3 attempts could most likely be transformed into a correct solution. (That is loosely called "debugging".) – Stephen C Commented Nov 23, 2024 at 2:12
• 2 Well ... why are they missing them? You don't need a "new approach". You need to understand why the existing code is behaving the way it does. That should be the goal of your debugging. – Stephen C Commented Nov 23, 2024 at 3:56
• 3 @OneCricketeer There is no such thing as a "java algorithm". You don't need a language tag to enable syntax highlighting, and SO is not a code writing service. People who follow language tags want to see questions about their language, and tend not to like questions about algorithms. Regardless of whether or not they "should", it is the way it is. – Matt Timmermans Commented Nov 23, 2024 at 16:00

 |  Show 6 more comments

2 Answers 2

Sorted by: Reset to default 3

Lemma 1

If you sort the list first, then there is an optimal solution that divides the list into 2 contiguous parts, a low part and a high part, such that numbers in the low part are only paired with numbers in the high part.

Proof

If an optimal solution does not have such a split, then it has numbers a,b,c,d in order, where a is paired with b and c is paired with d. In this situation, however, b and c can swap partners, so that a pairs with c and b pairs with d. This removes the violation of the splitting constraint involving those two pairs.

Given any optimal solution, we can apply this procedure repeatedly until the list can be split in 2.

Algorithm 1

Now that we know that we can split the list this way, we just have to find an appropriate splitting point. Then we can match elements in a greedy way -- the smallest low element pairs with the lowest possible high element, then the next-lowest, etc.

You can just try all the possible split positions, leading to an O(n²) algorithm.

We can do better than this, though...

Lemma 2

Given a solution divided into 2 parts as above, with P pairs, there is an equivalent solution in which all of the P lowest elements are paired with all of the P highest elements, in order.

This is easily proven with a similar partner-swapping proof.

Algorithm 2

As Kelly Bundy has shown, since there can be at most P=floor(n/2) pairs, the P elements that are paired with higher elements can always fit into the first half of the list, and the P elements paired with lower elements can always fit into the last half.

Therefore, we can just divide the list into halves and greedily match the first half with the second.

That would be an O(n) algorithm, except for the initial sort that makes it O(n log n).

Let's test with the example:

[2,1,2,4,1,4,1]

sort

[1,1,1,2,2,4,4]

P = 3, creating pairs (1,2), (1,2), (1,4)

Based on Matt's answer: Sort and then greedily try to pair right-half elements with left-half elements. O(n log n) for sorting and O(n) for the rest.

static int solve(List<Integer> arr) {
    arr.sort(null);
    int i = 0, n = arr.size();
    for (int j = (n+1)/2; j < n; j++)
        if (2 * arr.get(i) <= arr.get(j))
            i++;
    return i;
}

Attempt This Online!

本文标签： javaFind unique pairsStack Overflow