java - 设计可按出现频率排序的列表列表

Question

设置

我有一个整数对列表:( (1,2), (1,3), (2,5), (1,6), (2,8), (9,8), ( 8,11)等)。在给定的对中，数字必须不同，但是当您将列表视为一个整体时，会有很多重复。

虽然这些信息与问题并不严格相关，但每个数字代表一副牌中的一张牌(并且在 1 到 52 之间(包含 1 和 52))，并且每对代表玩家可能拥有的一张牌。

问题

我们想要对这些数字对进行排序，使得包含整个列表中最常见的卡片的数字对排在第一位。然后，这些对按第二个数字升序排序。然后我们使用列表中的剩余对重复该过程。打破平局的规则是较小的数字在前。让我们使用上面的列表来做一个例子:

1. 数字 1、8 和 2 在列表中各出现 3 次，并且没有数字出现超过 3 次。因此，有 3 路平局，1 胜。我们构建列表的第一部分如下:

   (1,2)
   (1,3)
   (1,6)
   

2. 剩余的列表项现在为 (2,5)、(2,8)、(9,8)、(8,11)。 8 出现了 3 次，比其他数字都多，因此 8 胜。我们继续我们的列表如下:

   (1,2)
   (1,3)
   (1,6)
   (2,8) <-- Note 2 is the smallest of the "other" numbers amongst the 8 group
   (9,8)
   (8,11)
   (2,5) <-- This gets added in step 3, but since there is only 1 left we add it now
   

回答标准

显然，我不期望任何人为我编写完整的算法，但我希望了解如何最好地设计它，也许还有一些小的伪代码。我的目标依次是效率、可读性和简单性。

具体:

• 我应该使用什么 Collections 对象来表示对和整个列表？
• 我是否应该在算法开始时对每个整数进行一次计数，然后在使用时通过减法来更新它们？或者我应该在每次通过后重做计数？前者似乎更有效率。
• 在一个阶段内，按对中的“其他”数字进行排序的最佳方式是什么？
• 出现平局时如何排序？

感谢您的意见。

Answer 1

我认为这不符合设计模式的资格。您确实需要考虑您的设计，但它需要是一个非常常见的问题才有资格成为模式，但事实并非如此。

public class CardAndPairs implements Comparable<CardAndPairs> {
    Card card;
    List<Pair> pairs;

    public CardAndPairs(Card card, Set<Pair> allPairs) {
       this.card = card;
       pairs = new HashSet<>();
       for (Pair pair : allPairs) 
         if (pair.contains(card))
           pairs.add(pair);
       // You could then reorder "pairs" by the value of the other card
       // ... see below
    }

    @Override
    public int compareTo(CardAndPairs other) {
       int diff = pairs.size() - other.pairs.size();
       if (diff > 0)
          return 1;
       if (diff == 0)
          return card.compareTo(other.card);
       return 1;
    }
}

然后，您可以将 52 张卡片的 CardAndPairs 放入列表中，并使用 compareTo 自动对它们进行排序(隐式使用 Collections.sort(list) )。 .

对给定 CardAndPairs 内的对进行排序在上面的构造函数中，以 Java 方式执行它会有点复杂。而不是直接使用 Pair ，您应该定义一个子类而不是实现 Comparable:

public class PairWithGivenCard 
          extends Pair implements Comparable<PairWithGivenCard> {
   Card givenCard;
   Card otherCard;

   public PairWithGivenCard(Card givenCard, Pair pair) {
      this.givenCard = givenCard;
      for (Card card : pair) // or however you get the cards from pair
         if (card != givenCard)
            otherCard = card;
   }

   @Override
   public int compareTo(PairWithGivenCard otherPair) {
      // It might be a good idea to throw 
      //   some exception if givenCard != otherPair.givenCard
      return otherCard.compareTo(otherPair.otherCard);
   }
}

然后您需要更改 List<Pair> pairs通过List<PairWithGivenCard> pairs在 CardAndPairs 的构造函数中。当您将一对添加到列表中时，您必须执行 pairs.add(new PairWithGivenCard(card, pair))而不是pairs.add(pair) 。最后你只需调用 Collections.sort(pairs)在 CardAndPairs 的构造函数末尾.