How to find the max value of any duplicate in an ArrayList

Question

I am currently writing class that creates multiple hands containing card objects using arrayLists. I am trying to write a method that searches an arraylist (hand) and returns the largest pair of cards.

Here is what I have now but it is very inefficient:

public int findPairRank() {
    int one = 0, two = 0, three = 0, four = 0, five = 0, six = 0, seven = 0, eight = 0, nine = 0, ten = 0, eleven = 0, twelve = 0, thirteen = 0;

    // loops through every card rank and adds +1 if it exists in the hand
    for (int i = 0; i < cards.size(); i++) {
        if (cards.get(i).getRank() == 1)
            one++;
        if (cards.get(i).getRank() == 2)
            two++;
        if (cards.get(i).getRank() == 3)
            three++;
        if (cards.get(i).getRank() == 4)
            four++;
        if (cards.get(i).getRank() == 5)
            five++;
        if (cards.get(i).getRank() == 6)
            six++;
        if (cards.get(i).getRank() == 7)
            seven++;
        if (cards.get(i).getRank() == 8)
            eight++;
        if (cards.get(i).getRank() == 9)
            nine++;
        if (cards.get(i).getRank() == 10)
            ten++;
        if (cards.get(i).getRank() == 11)
            eleven++;
        if (cards.get(i).getRank() == 12)
            twelve++;
        if (cards.get(i).getRank() == 13)
            thirteen++;
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    if (one == 2)
        list.add(1);
    if (two == 2)
        list.add(2);
    if (three == 2)
        list.add(3);
    if (four == 2)
        list.add(4);
    if (five == 2)
        list.add(5);
    if (six == 2)
        list.add(6);
    if (seven == 2)
        list.add(7);
    if (eight == 2)
        list.add(8);
    if (nine == 2)
        list.add(9);
    if (ten == 2)
        list.add(10);
    if (eleven == 2)
        list.add(11);
    if (twelve == 2)
        list.add(12);
    if (thirteen == 2)
        list.add(13);

    int max = 0;
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) > max)
            max = list.get(i);
    }
    if (max > 0)
        return max;
    else
        return 0;
}

You could trivially implement a multiset with `Map`, whether the Integer is the count. Then you could just iterate over it and find the largest count. — Kevin, Jan 30 '17 at 20:21
Do you mean the runtime inefficient, or is the code is bulky? — MeetTitan, Jan 30 '17 at 20:22
@MeetTitan That the code is bulky! I feel like I could use a double nested array list to do it in far less code. — Wiz, Jan 30 '17 at 22:27

AdamSkywalker · Answer 1 · 2017-01-30T20:50:16.360

1

Note: better use map counter solution. this algorithm works, but I would not use it. It looked nice at the beginning, until Zhong Yu pointed to a problem.

Sort cards in hand by value, then iterate until you find a pair

// copy items to new list to preserve initial order
List<Card> cards = new ArrayList(playerCards); 
// sort cards by rank value from high to low
Collections.sort(cards, rankComparator);

int counter = 1; // number of cards of same rank
for (int i = 1; i < cards.size(); i++) {
    if (cards.get(i).getRank() == cards.get(i-1).getRank()) {
        counter++; // if card has same rank as previous, inc counter
    } else { // if rank changed
        if (counter == 2) { // if we had pair, return its rank
           return cards.get(i-1).getRank();
        } else { // start again
           counter = 1;
        }
    }
}    
return counter == 2 ? cards.get(i-1).getRank() : 0;

edited Jan 30 '17 at 20:50

answered Jan 30 '17 at 20:23

AdamSkywalker

11,408
3
38
76

Since we want to find max pair, we could look at the sorted list from n to 1. How about changing for loop like this, for ( int i = cards.size()-1; i>=0;i--)? – exiter2000 Jan 30 '17 at 20:28
@exiter2000 I assume that comparator is in decreasing order, so it puts highest card first – AdamSkywalker Jan 30 '17 at 20:30
it may return something more than a pair - 3 or 4 of a kind – ZhongYu Jan 30 '17 at 20:33
@Adam, if it has reverse ordering comparator implemented, it totally make sense. – exiter2000 Jan 30 '17 at 20:35

score 1 · Answer 2 · answered Jan 30 '17 at 20:36

The code seems ok but it is very cumbersome as your repeat many things that should not be.
In the loop you could use a Map to associate card number with occurrence.
In this way you avoid the long series of if statements.

The code could look like that:

    List<Card> cards = ...
    Map<Integer,Integer> occurrenceByNumber = new HashMap<>();
    for (int i = 0; i < cards.size(); i++) {
        Card card = cards.get(i);
        Integer occurrence = occurrenceByNumber.get(card.getRank());
        if (occurrence == null){
            occurrence = 1;
        }       
        else{
           occurrence++;
        }   
        occurrenceByNumber.put(card.getRank(), occurrence);        
    }


    Integer maxNumber = null;
    for (Entry<Integer, Integer> entry : occurrenceByNumber.entrySet()){
        int occurrence = entry.getValue();
        int number = entry.getKey();
        if ( occurrence == 2 && (maxNumber == null || number> maxNumber)  ){
            maxNumber = number;
        }
    }

    return maxNumber;

score 1 · Accepted Answer · answered Jan 30 '17 at 22:06

1

Because common card games only have 13 different card rankings, it is possible to avoid the use of Maps. You just need a frequency counter for rankings on an int[13] (or even byte[13]) temp array. Here is an example:

public int findPairRank() {
    int[] freq = new int[13];
    for (Card c: cards) { //assuming you use Card objects
        freq[c.getRank()]++;
    }

    for (int i = 12; i >= 0; i--) {
        if (freq[i] == 2) return i;
    }
    return -1; //no pair found
}

*Note that typically the number 2 card has the lowest ranking (in my example rank = 0) and the Ace the highest one (in my example rank for aces is 12). You can easily change the above according to your ranking design.

answered Jan 30 '17 at 22:06

Kostas Kryptos

4,081
2
23
24

`freq[c.getRank()]++;` will rise a `ArrayIndexOutOfBoundsException` when `c.getRank()` returns `13` since the `freq` array has a length of 13. Consequently, the last index value usable is `12`. – davidxxx Jan 30 '17 at 22:27
I noted that this is for 0-12; this is easy for the OP to change according to his reqs. – Kostas Kryptos Jan 30 '17 at 22:29
I do really like this answer since it uses an array to solve the problem which was my original intention!. Ill try this out and report back. – Wiz Jan 30 '17 at 22:40
ok, as @davidxxx commented, I see you are using ranking for 1-13 and the example is for 0-12. Let me know if you experience difficulties to transform it to 1-13 (just some additions/subtractions on the indices and then return 0 instead of -1) – Kostas Kryptos Jan 30 '17 at 22:43
1

@Wiz Indeed, it is a good way to address the problem :) @Konstantinos Chalkias instead of additions on the indexes I would rather declare a array of 14 elements `int[] freq = new int[14];` I find that it makes the code clearer and natural even if the first element is not used. – davidxxx Jan 30 '17 at 22:48
sure @davidxxx, that could also work too; less verbose! – Kostas Kryptos Jan 30 '17 at 22:49
@davidxxx & Konstantinos Chalkis It worked exactly how I wanted! I changed the int[] array to hold 14 values and i made the for loop that checks for frequency start at 13 and end at 1. Thanks so much guys!!! I couldnt figure this out for the life of me yesterday. – Wiz Jan 30 '17 at 22:55
Thanks, don't forget to return 0 if a pair is not found – Kostas Kryptos Jan 30 '17 at 22:56
Thank you! I had a quick question actually @Konstantinos Chalkias. I am unfamiliar with using : in a for loop. Does this just mean that as long as there are more cards in the card set array list, it will keep running the loop? – Wiz Jan 30 '17 at 23:00
Yes iterating over the whole list. Check this link http://stackoverflow.com/questions/18410035/ways-to-iterate-over-a-list-in-java – Kostas Kryptos Jan 30 '17 at 23:04

score 0 · Answer 4 · answered Jan 30 '17 at 20:26

ArrayList<Integer> hand = new ArrayList<Integer>(13);
for (int i = 0; i < cards.size(); i++) {
    int x = cards.get(i).getRank();
    if(x>0&&x<14) {
         hand.set(i-1, hand.get(i-1)+1)); //increment values
    }
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<hand.size(); i++) {
     if(hand.get(i)==2) {
          list.add(i+1); //one will be at index 0, etc
     }
}

return Collections.max(list);

score 0 · Answer 5 · answered Jan 30 '17 at 20:40

Here's how I would approach this problem:

1) Sort the hand on card rank from greatest rank to least rank.

2) Iterate over the cards in the sorted hand, finding the !first! instance of when the next card's ranking is the same as this card's ranking. if (cards.get(i+1).getRank() == cards.get(i).getRank())

3) Done.

Note, the above code is NOT efficient! You can make minor changes to retain card rankings between loop iterations to make the code even more efficient.

How to find the max value of any duplicate in an ArrayList

5 Answers5